点击刷新
Source: The 10th Shandong Provincial Collegiate Programming Contest
题解：
因为2^p为偶数，所以a，x的奇偶性相同
1.当a为奇数时，答案始终为1
2.下面讨论a为偶数的情况
因为a为偶数，所以a=2*other，a^x=2^x*other^x；
当x>=p时，a^x%2^p==0，此时只需要关心x^a%2^p==0，即x^a是2^p的倍数；
因为x为偶数，所以x=2^q*tmp，x^a=(2^q)^a*tmp^a=2^qa*tmp^a；
另tmp==1，并让2^qa>=2^p,即qa>=p,解得q>=p/a向上取整，满足x^a是2^p的倍数的q的最小值（也就是说x中必须要包含一个2^q才能是2^p的倍数）；
由于1<=x<=2^p，故ans+=(2^p)/(2^q)-(p-1)/(2^q)；
当x<p时，可以直接暴力
AC代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn=1e5+50; 5 ll a,p,mod,ans; 6 ll qpow(ll x,ll y) 7 { 8 ll res=1; 9 while(y){ 10 if(y%2==1) res=res*x%mod; 11 x=x*x%mod; 12 y>>=1; 13 } 14 return res; 15 } 16 int main() 17 { 18 int t; 19 for(scanf("%d",&t);t;t--) 20 { 21 mod=1;ans=0; 22 scanf("%lld %lld",&a,&p); 23 if(a%2==1) 24 { 25 printf("1\n"); 26 continue; 27 } 28 mod<<=p; 29 for(ll i=2;i<p;i+=2) 30 { 31 if(qpow(i,a)==qpow(a,i)) ans++; 32 } 33 ll q=(p-1)/a+1; 34 ll cnt=1;cnt<<=q; 35 ans+=mod/cnt-(p-1)/cnt; 36 printf("%lld\n",ans); 37 } 38 return 0; 39 }
© 著作权归作者所有
举报
发表评论
0/200
