2015年1月11日 星期日

Codechef January Challenge 2015 Sereja and LCM

/*
    排容原理
*/
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;
#define MOD 1000000007

int pow(int x, int n)
{
    if( n == 0 ) return 1;

    int half = pow(x, n/2);

    if( n&1 ) return (ll)half*half%MOD*x%MOD;
    else return (ll)half*half%MOD;
}

int T;
int N, M, L, R;

int main()
{
    scanf("%d", &T);

    while( T-- )
    {
        scanf("%d %d %d %d", &N, &M, &L, &R);

        int Ans = 0;

        for(int i = L; i <= R; i++)
        {
            int p = i;
            vector<int> v;

            for(int j = 2; j*j <= p; j++)
            {
                if( p%j == 0 )
                {
                    int x = 1;

                    while( p%j == 0 )
                    {
                        p /= j;
                        x *= j;
                    }

                    v.push_back(x);
                }
            }

            if( p != 1 ) v.push_back(p);

            int now = 0, n = v.size();

            for(int j = 1; j < (1<<n); j++)
            {
                int cnt = 0, val = 1, num = 0; vector<int> r;

                for(int bi = 0, vi = 1; bi < n; bi++, vi <<= 1)
                {
                    if( vi&j )
                    {
                        val *= v[bi];
                        cnt++;
                        r.push_back(v[bi] );
                    }
                }

                int m = r.size();

                for(int k = 1; k < (1<<m); k++)
                {
                    int cnt2 = 0, val2 = 1;

                    for(int bj = 0, vj = 1; bj < m; bj++, vj <<= 1)
                    {
                        if( vj&k )
                        {
                            val2 *= r[bj];
                            cnt2++;
                        }
                    }

                    if( cnt2%2 == 1 ) num += M/val2;
                    else num -= M/val2;
                }

                if( cnt%2 == 1 ) now += pow(M-num, N);
                else now -= pow(M-num, N);

                now = (now%MOD+MOD)%MOD;
            }

            Ans += pow(M, N)-now;
            Ans = (Ans%MOD+MOD)%MOD;
        }

        printf("%d\n", Ans);
    }
}

沒有留言:

張貼留言