题目

传送门

题解

根据费马小定理 ： a^i 同余 a^(i+(p-1)j) (mod p)
又因为 a 同余 a+pi (mod p)
设 n = (p-1)j+i
则有
na^n 同余 b (mod p)
则有 na^((p-1j)+i) 同余 b (mod p)
则 n*a^i 同余 b (mod p)
则 ((p-1)*j+i)*a^i 同余 b (mod p)
则有 (i-j)*a^i 同余 b (mod p)

update:
求出最小的n,则x/(p*(p-1))+(x%(p*(p-1))>=n)则为方案
就有 (i-j) 同余 b/a^i(mod p)
因为我们求最小值 所以 i-j=b/a^i(i<p(否则会导致i又会消掉)且(p-1)j+i<=p(p-1))
b/a^i 同余 b*inv(a^i) (mod p)

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn = 5e3+5;
typedef long long LL;
#define int LL
int readint(){
int x=0,f=1;char s=getchar();
#define sc (s=getchar())
while(s<'0'||s>'9'){
if(s=='-')
f=-1;
sc;
}
while(s>='0'&&s<='9'){
x=(x<<3)+(x<<1)+(s^48);
sc;
}
#undef sc
return x*f;
}
int p;
int qkpow(int a,int b){
int ans=1;
while(b){
if(b&1)
ans=1ll*ans*a%p;
b>>=1;
a=a*a%p;
}
return ans;
}
int a,b,x;
signed main(){
a=readint(),b=readint(),p=readint(),x=readint();
int ans=0;
for(int i=1;i<p;i++){
int inv=qkpow(qkpow(a,i),p-2)%p;
int j=(i-b*inv%p+p)%p;
int n=((p-1)*j+i)%(p*(p-1));
if(n==0)
n=p*(p-1);
ans+=x/(p*(p-1))+(x%(p*(p-1))>=n);
}
cout<<ans;
return 0;
}
/*
根据费马小定理 ： a^i 同余 a^(i+(p-1)*j) (mod p)
又因为 a 同余 a+p*i (mod p)
设 n = (p-1)*j+i
则有
n*a^n 同余 b (mod p)
则有 n*a^((p-1*j)+i) 同余 b (mod p)
则 n*a^i 同余 b (mod p)
则 ((p-1)*j+i)*a^i 同余 b (mod p)
则有 (i-j)*a^i 同余 b (mod p)
update:
求出最小的n,则x/(p*(p-1))+(x%(p*(p-1))>=n)则为方案
就有 (i-j)
同余 b/a^i(mod p)
因为我们求最小值 所以 i-j=b/a^i(i<p(否则会导致i又会消掉)且(p-1)*j+i<=p*(p-1))
b/a^i 同余 b*inv(a^i) (mod p)
*/

最后

以上就是冷静酒窝为你收集整理的CF919-E题目题解的全部内容，希望文章能够帮你解决CF919-E题目题解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。