2019山东省赛K - Happy Equation ZOJ - 4123 题解
题意：
一个数论题，要求满足如下等式的x有多少个。
思路：
当时比赛是，队伍看到这个题，也没有做太多的思考，就是无从下手，几乎放弃。但是看到学校另外两支队伍都过了这个题，感觉自己还是好菜。
打表可以发现，当a为奇数的时候答案为1。当a为偶数的时候，x一定也是偶数，这个还是比较明显的。
对左边进行推导，因为a为偶数，设a=2*t，所以a^x=2^x*t^x,所以当x大于p时，这个求余之后一定为0。由于p很小，可以直接暴力求解，所以对于右边直接考虑x^a求余之后为0的x的情况。由于x为偶数。我们再次对x分解，设x=2^k*t,就是把x写成一个2的 次幂和t的乘积的形式，所以x^a=2^(ka)*t^a，所以只需要ka>=p,就可以满足条件，而且只有ka>=p可以满足条件，因为t^a不可能可以整除，所以现在要求k>=p/a，对p/a取上整即可，就是考察有多少个t，在1-up的范围内（up为x的上界），个数为up/ceil(p/a)/2^k。当然最后的答案要减去1-p范围内的数，因为这一部分是特殊考虑的。
代码：
1 #include <iostream> 2 #include<cmath> 3 #include<stdio.h> 4 //a^x 与x^a 5 // 1<=x<=2^p 6 using namespace std; 7 #define ll long long 8 ll ppow(int x,int n,ll mod) 9 { 10 ll res=1; 11 ll base=x; 12 while(n) 13 { 14 if(n&1) 15 res=(res*base)%mod; 16 base=(base*base)%mod; 17 n>>=1; 18 } 19 return res%mod; 20 } 21 int main() 22 { 23 int a,p; 24 int T; 25 while(~scanf("%d",&T)) 26 { 27 while(T--) 28 { 29 scanf("%d%d",&a,&p); 30 31 if(a%2) 32 { 33 cout<<1<<endl; 34 continue; 35 } 36 //x>=p 37 ll up=(1LL<<p); 38 ll ans=0; 39 for(int i=1;i<=p;i++){ 40 if(ppow(a,i,up)==ppow(i,a,up))ans++; 41 } 42 ll tem=ceil(p/(a+0.0)); 43 ans+=(up>>tem)-(p>>tem); 44 cout<<ans<<endl; 45 } 46 } 47 48 return 0; 49 }
投递柠檬微趣等公司10个岗位 >
