首页 > 代码库 > Power Sum 竟然用原根来求

Power Sum 竟然用原根来求

2024-07-13 22:31:09   225人阅读

 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

21 1 113 2 11

Sample Output

13

Hint

i^m即求 i * i * i * i * i... * i(m个i)，比如2^3即2 * 2 * 2 
 
 1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <math.h> 5 #include <algorithm> 6 using namespace std; 7 #define ll long long 8 int fac[100],fn,pri[1100],pn=0; 9 void init()10 {11     int i,j;12     for(i=2;i<1100;i++)13     {14         if(!pri[i])15         {16             pri[pn++]=i;17             j=i*i;18             while(j<1100)19             {20                 pri[j]=1;21                 j+=i;22             }23         }24     }25 }26 void findfac(int x)27 {28     fn=0;29     int i,j;30     for(i=0;x>=pri[i]&&i<pn;i++)31     {32         if(x%pri[i]==0)33         {34             fac[fn++]=pri[i];35             while(x%pri[i]==0)x/=pri[i];36         }37     }38     if(x!=1)fac[fn++]=x;39 }40 ll power(ll x,ll y,ll mod)41 {42     ll ans=1;43     while(y)44     {45         if(y&1)46         {47             ans*=x;48             ans%=mod;49         }50         x*=x;51         x%=mod;52         y>>=1;53     }54     return ans;55 }56 bool check(ll x,ll y)57 {58     ll z=y-1;59     for(ll i=0;i<fn;i++)60     if(power(x,z/fac[i],y)==1)return 0;61     return 1;62 }63 int findroot(int x)64 {65     if(x==2)return 1;66     findfac(x-1);67     for(ll i=2;;i++)68     if(check(i,x))return i;69 }70 int poww[1100000],repow[1100000];71 int dp[1100000];72 int main()73 {74     init();75     int t,root,i,j;76     ll n,m,p;77     scanf("%d",&t);78     while(t--)79     {80         scanf("%lld%lld%lld",&n,&m,&p);81         root=findroot(p);82         m%=p-1;83         int temp=1;84         for(i=0;i<p;i++)85         {86             poww[i]=temp;87             repow[temp]=i;88             temp=temp*root%p;89         }90         dp[0]=0;91         for(i=1;i<p;i++)92         {93           dp[i]=(dp[i-1]+poww[(repow[i]*m)%(p-1)])%p;94         }95         printf("%d\n",dp[n%p]);96     }97 }
View Code

 


联系
我们