Law of Commutation
题目大意:给你n和a,问在【1,2】中有多少个b满足 a%m=b%m,其中m=2
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6189
解题思路:先打表,找一下规律
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,a; ll qpow(ll a,ll b,ll m) { ll ans=1; a=a%m; while(b) { if(b%2) ans=ans*a%m; a=a*a%m; b=b/2; } return ans; } ll qpow(ll a,ll b) { ll ans=1; while(b) { if(b%2) ans=ans*a; b=b/2; a=a*a; } return ans; } int main() { while(cin>>n>>a) { ll m=1<<n; ll ans=0; for(int i=1;i<=m;i++) { if(qpow(a,i,m)==qpow(i,a,m)) ans++; } cout<<ans<<endl; } return 0; }
我们可以发现,当a为奇数的时候,答案永远是1,所以就需要讨论a是偶数的时候的情况
若a是偶数则a也一定是偶数,所以b必须为偶数,则a=2*x ,a=2*x,当b>=n的时候,a
%m==0,所以可以找到当b<n的时候有多少符合题意的接,若b>=n,则b%m==0,b=2*y
b=2*y %(2)==0,则此时应使得ax>=n,x>=n/a,因此我们只需要计算出最小的x并求得在m的范围内
2
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,a; ll qpow(ll a,ll b,ll m) { ll ans=1; a=a%m; while(b) { if(b%2) ans=ans*a%m; a=a*a%m; b=b/2; } return ans; } ll qpow(ll a,ll b) { ll ans=1; while(b) { if(b%2) ans=ans*a; b=b/2; a=a*a; } return ans; } int main() { while(cin>>n>>a) { if(a%2==1) { cout<<"1"<<endl; continue; } else { ll m=1<<n; ll ans=0; for(int i=1;i<=n;i++) { if(qpow(a,i,m)==qpow(i,a,m)) ans++; } ll b2=n/a; if(b2*a<n) b2++; ll b3=pow(2,b2); ll res1=m/b3-n/b3; cout<<ans+res1<<endl; } } return 0; }