Power Sum 竟然用原根来求

Power Sum

Time Limit: 20000/10000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)SubmitStatus

Problem Description

给出n,m,p，求 (1^m + 2^m + 3^m + 4^m + … + n^m) % p

Input

第一行一个数T( <= 10),表示数据总数

然后每行给出3个数n,m,p(1 <= n <= m <= 10^18, 1 <= p <= 10^6, p是质数

Output

每组数据输出你求得的结果

Sample Input

2
1 1 11
3 2 11

Sample Output

1
3

Hint

i^m即求 i * i * i * i * i… * i(m个i)，比如2^3即2 * 2 * 2  

 #include <iostream>
 #include <stdio.h>
 #include <string.h>
 #include <math.h>
 #include <algorithm>
 using namespace std;
 #define ll long long
 int fac[],fn,pri[],pn=;
 void init()
 {
     int i,j;
     for(i=;i<;i++)
     {
         if(!pri[i])
         {
             pri[pn++]=i;
             j=i*i;
             while(j<)
             {
                 pri[j]=;
                 j+=i;
             }
         }
     }
 }
 void findfac(int x)
 {
     fn=;
     int i,j;
     for(i=;x>=pri[i]&&i<pn;i++)
     {
         if(x%pri[i]==)
         {
             fac[fn++]=pri[i];
             while(x%pri[i]==)x/=pri[i];
         }
     }
     if(x!=)fac[fn++]=x;
 }
 ll power(ll x,ll y,ll mod)
 {
     ll ans=;
     while(y)
     {
         if(y&)
         {
             ans*=x;
             ans%=mod;
         }
         x*=x;
         x%=mod;
         y>>=;
     }
     return ans;
 }
 bool check(ll x,ll y)
 {
     ll z=y-;
     for(ll i=;i<fn;i++)
     if(power(x,z/fac[i],y)==)return ;
     return ;
 }
 int findroot(int x)
 {
     if(x==)return ;
     findfac(x-);
     for(ll i=;;i++)
     if(check(i,x))return i;
 }
 int poww[],repow[];
 int dp[];
 int main()
 {
     init();
     int t,root,i,j;
     ll n,m,p;
     scanf("%d",&t);
     while(t--)
     {
         scanf("%lld%lld%lld",&n,&m,&p);
         root=findroot(p);
         m%=p-;
         int temp=;
         for(i=;i<p;i++)
         {
             poww[i]=temp;
             repow[temp]=i;
             temp=temp*root%p;
         }
         dp[]=;
         for(i=;i<p;i++)
         {
           dp[i]=(dp[i-]+poww[(repow[i]*m)%(p-)])%p;
         }
         printf("%d\n",dp[n%p]);
     }
 }