The 10th Shandong Provincial Collegiate Programming Contest
思路:a,x的奇偶性相同(因为都对偶数取模),且打表得出a为奇数时,答案为1。(¿)
a为偶数时,令 a=t1*2q → ax=t1x*2qx
若axmod2p为0,则qx>=p,x>=p/q;由于q>=1(a为偶数),则x>=p;
x与a同为偶数,令x'=t2*2k → x'a=t2a*2ka
若x'amod2p为0,则ka>=p,k>=p/a(上取)=k';
在[p,2p]中,x取2k'的倍数即可满足xamod2p为0,个数有2p-k'-(p-1)/2k'
在[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; }
- Programming Provincial Collegiate Shandong Contestprogramming collegiate provincial shandong programming provincial collegiate shandong programming collegiate provincial contest programming provincial collegiate sichuan programming collegiate provincial guangdong programming collegiate provincial counting programming provincial collegiate sponsored 2023 programming collegiate provincial 题解programming collegiate provincial programming collegiate jiangsu contest