CF#460 E Congruence Equation

标签：int cdot Equation Congruence CF pmod ans LL equiv

求满足

\[n\cdot a^n\equiv b\pmod{p} \]

的 \(n(1<n<x)\) 的个数，令\(n=(p-1)t+k (0\le k <q-1)\)，那么

\[n\equiv b\cdot a^{-k} \pmod{p} \]

那么枚举 \(k\)，求满足条件的 \(t\) 的个数。

\begin{align}
(k-t)\equiv b\cdot a^{-k}\pmod{p}
\end{align}

\[(k-b\cdot a^{-k})\equiv t\pmod{p} \]

即

\[ (p-1)(k-b\cdot a^{-k})+k\equiv (p-1)t+k\pmod{p} \]

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int a, b, p;
LL x;

inline int pow(int a, int b, int p){
	LL ans = 1, base = a;
	while (b){
		if (b & 1){
			(ans *= base) %= p;
		}
		(base *= base) %= p;
		b >>= 1;
	}
	return (int)ans;
}

inline int inv(int x, int p){
	return pow(x, p - 2, p);
}

int main(){
	scanf("%d%d%d%I64d", &a, &b, &p, &x);
	LL ans = 0;
	for (int i = 1; i <= p - 1; i++){
		int now = (LL)b * inv((LL)pow(a, i, p), p) % p;
		LL first = (LL)(p - 1) * ((i - now + p) % p) + i;
		if (first > x) continue;
		ans += (x - first) / ((LL)p * (p - 1)) + 1;
	}
	printf("%I64d\n", ans);
}

标签：int,cdot,Equation,Congruence,CF,pmod,ans,LL,equiv
From： https://www.cnblogs.com/shinidetiehanhan/p/16741674.html