E. Congruence Equation
果然 chinese round , 很有中国特色, 打得血崩 -_-
题意: 给出 abpx p 是质数
find out how many positive integers n (1nx) satisfy
tags:
1 首先这个指数肯定先化掉, 由费马小定理 a^(p-1) = 1 , 则定 n = i(p-1)+j, 那么
[ i(p-1)+j ] * a ^j = b (%p)
i(p-1)+j = b * a^-j (%p) , 设 y = b * a^-j ,
- i = (y-j) / (p-1) (%p)
- i = (y-j) / (p-1) + k*p
由于 n = i(p-1) + j
i = (n-j) / (p-1)
2 所以我们枚举 j 从 0 ~ p-2, 每次看有多少个 i 符合 1<= n <= x 的条件即可
- // 460 E
- #include<bits/stdc++.h>
- using namespace std;
- #pragma comment(linker, "/STACK:102400000,102400000")
- #define rep(i,a,b) for (int i=a; i<=b; ++i)
- #define per(i,b,a) for (int i=b; i>=a; --i)
- #define mes(a,b) memset(a,b,sizeof(a))
- #define INF 0x3f3f3f3f
- #define MP make_pair
- #define PB push_back
- #define fi first
- #define se second
- typedef long long ll;
- const int N = 200005;
- ll a, b, p, x;
- ll fpow(ll a, ll b, ll mod) {
- ll ans = 1;
- for(a%=mod ; b; b>>=1, a=a*a%mod)
- if(b&1) ans = ans*a%mod;
- return ans%mod;
- }
- int main()
- {
- scanf("%lld%lld%lld%lld", &a, &b, &p, &x);
- ll ans = 0;
- for(ll j=0; j<p-1; ++j)
- {
- ll y = b*fpow(fpow(a,p-2,p), j, p)%p;
- ll i1 = (y-j+p)%p * fpow(p-1,p-2,p)%p;
- if(i1*(p-1)+j > x) continue;
- ll i2 = (x-j)/(p-1);
- ans += (i2-i1)/p+1;
- }
- printf("%lld\n", ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2487218.html