Description
给定整数 (x),求有多少个正整数 (n) 满足 (1 le n le x) 且 (na^n equiv b mod p),(p le 10^6 + 3) 且是一个质数,(x le 10^{12})。
Solution
(n) 因子的循环周期为 (p),(a^n) 因子的循环周期为 (p-1)
(由于模质数乘法构成循环群满足消去律,其运算表的任意行列为元素全排列)
[n equiv ba^{-n} (mod p)
]
枚举 (n),设 (delta = n-ba^{-n} mod p),则 (n'=n+(p-1)delta) 才是第一个正确的 (n)
于是这一步贡献 ([frac {x-n'} {p(p-1)}])
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
int a,b,mod,x,ans;
int qpow(int p,int q)
{
return (q&1 ? p : 1) * (q ? qpow(p*p%mod,q>>1) : 1) % mod;
}
int inv(int p)
{
return qpow(p, mod-2);
}
signed main()
{
ios::sync_with_stdio(false);
cin>>a>>b>>mod>>x;
for(int i=1;i<=min(x,mod-1);i++)
{
int n=i+(mod-1)*((i-b*inv(qpow(a,i))%mod+mod)%mod);
if(x>=n) ans+=(x-n)/(mod*(mod-1))+1;
}
cout<<ans<<endl;
}