本文主要是介绍Codeforces Round #460 (Div. 2) E. Congruence Equation 数学,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
E. Congruence Equation
solution
{ i ∗ a i % p = b , i < p − 1 , ( t − k ) ∗ a t % p = b , i ≥ p − 1 , i = ( p − 1 ) k + t . \begin{cases} i*a^i\%p=b,i<p-1, \\(t-k)*a^{t}\%p=b,i≥p-1,i=(p-1)k+t. \end{cases} {i∗ai%p=b,i<p−1,(t−k)∗at%p=b,i≥p−1,i=(p−1)k+t.
分别枚举 i , t . i,t. i,t.
code
/*SiberianSquirrel*/
/*CuteKiloFish*/
#include<bits/stdc++.h>using namespace std;
typedef long long ll;const double PI = acos(-1), eps = 1e-8;
/*const int MOD = 998244353, r = 119, k = 23, g = 3;
const int MOD = 1004535809, r = 479, k = 21, g = 3;*/
const int INF = 0x3f3f3f3f, MOD = 1e9 + 7;
const int M = 1e7 + 10, N= 2e6 + 10;int sgn(double x) {if(fabs(x) < eps) return 0;return x < 0? -1: 1;
}
//inline int rnd(){static int seed=2333;return seed=(((seed*666666ll+20050818)%998244353)^1000000007)%1004535809;}
//double Rand() {return (double)rand() / RAND_MAX;}ll a, b, p, x;
int inv[N];void solve(ll res = 0) {ll temp = a;for(int i = 1; i < min(p - 1, x + 1); ++ i) {if(1ll * i * temp % p == b) res ++;temp = temp * a % p;}temp = 1;for(int i = 0; i <= p - 2; ++ i) {ll t = ((b * inv[temp] - i + p) % p) * inv[p-1] % p;res += ((x - i) / (p - 1) - t) / p;if((t && t * (p - 1) + i <= x)) res ++;temp = temp * a % p;}cout << res << endl;
}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(nullptr);
// srand(time(0));
#ifdef ACM_LOCALfreopen("input", "r", stdin);freopen("output", "w", stdout);
#endifint o = 1;
// cin >> o;while(o --) {cin >> a >> b >> p >> x;inv[1] = 1;for(int i = 2; i < N; ++ i)inv[i] = 1ll * (p - p / i) * inv[p % i] % p;solve();}return 0;
}
这篇关于Codeforces Round #460 (Div. 2) E. Congruence Equation 数学的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!