The 10th Shandong Provincial Collegiate Programming Contest

The 10th Shandong Provincial Collegiate Programming Contest

K - Happy Equation

思路：a，x的奇偶性相同（因为都对偶数取模），且打表得出a为奇数时，答案为1。（¿）

a为偶数时，令 a=t₁*2^q   → a^x=t₁^x*2^qx

若a^xmod2^p为0，则qx>=p，x>=p/q；由于q>=1（a为偶数），则x>=p；

x与a同为偶数，令x'=t₂*2^k → x'^a=t₂^a*2^ka

若x'^amod2^p为0，则ka>=p，k>=p/a(上取)=k'；

在[p，2^p]中，x取2k'的倍数即可满足x^amod2p为0，个数有2^p-k'-(p-1)/2^k'

在[1，p）中，枚举x即可；(p<=30)

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;
int mmod;
int ksm(int x,int y){
    int res=1;
    while(y){
        if(y&1)res=res*x%mmod;
        x=x*x%mmod;
        y>>=1;
    }
    return res;
}
void solve(){
    int a,p;cin>>a>>p;
    mmod=1<<p;
    if(a&1){
        cout<<"1\n";return ;
    }
    int ans=0;
    for(int i=1;i<p;++i)
        ans+=ksm(a,i)==ksm(i,a);
    int y=(p+a-1)/a;
    ans+=(1<<(p-y))-(p-1)/(1<<y);
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //init();
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}