题解 CF919E 【Congruence Equation】
interestingLSY
2018-02-01 22:04:16
# CF919E Congruence Equation 题解
先说一句话:
请诸位大佬饶恕我的语言表达能力。。。。
## 看一眼
乍一看数据范围, $x \leq 10^{12}$ , 大的可~~啪~~
然而 $p \leq 10^6+3$, 说明也许可以在 $p$ 上开刀,利用周期性等奇怪性质搞事情
## 再看一眼
我看到了mod
可以发现:
因为p为质数,所以
- $n ≡ n+p{\color{Blue}{\pmod{p}}}$
- ${a^n} ≡ {a^{n+p-1}}{\color{Blue}{\pmod{p}}}$ 可用费马小定理证明
↑说真的我也不知道上面的该怎样表达qwqwqwq。。。
反正意思就是在%p的意义下$n=n+p$ , ${\ a^n}=a^{\ n+p-1}$
因此,我们可以**利用n的周期性**通过这样一种方法:
只要枚举所有 $a^n\ mod\ p \ ( 1 \leq n < p\ )$ , 并分别统计答案就行
顺便提一句:蓝色的不是超链接awa
## 问题来了。。。
怎么统计答案?
请注意:并不是对于所有 $a^n\ mod\ p \ ( 1 \leq n < p\ )$ ,答案都存在。
假设我们现在枚举的$a^n$中的n为 $i$ , 此时满足 $n \times a^n\ mod\ p\ = \ b$ 的n为 $j$
那么一定会有
$ j ≡ i {\color{Blue}{\pmod{p-1}}}$
$ j ≡ b \times Inv\ (a^{\ i}\ ) {\color{Blue}{\pmod{p}}} \quad$其中 $Inv\ (a^{\ i}\ )$表 $a^{\ i}$ 在 $mod\ p$ 意义下的逆元
提示:第二个式子是用 $j \times a^{\ i}\ mod\ p\ = \ b$ 导出的。
接下来么...解一下这个方程组就OK
## 代码
为了方便大家~~直接复制粘贴~~看代码,这里只放出关键部分
```cpp
ll a,b,p;
ll x;
il ll Qpow( ll a , ll b ){
a %= p;
ll ret = 1LL;
while(b){
if(b&1){
ret *= a;
ret %= p;
}
a *= a;
a %= p;
b >>= 1LL;
}
return ret % p;
}
il ll Inv( ll x ){
return Qpow(x,p-2) % p;
}
ll Mod( ll x , ll mod ){
return ((x%mod)+mod)%mod;
}
ll ans = 0LL;
// 解方程
ll Cal( int n , int power ){
ll now = b * Inv(power) % p;
ll correctn = (p-1)*Mod(n-now,p) + n;
if( correctn > x ) return 0LL;
return (x-correctn) / (p*(p-1)) + 1;
}
int main(){
cin >> a >> b >> p >> x;
ll power = 1;
For(n,p-1){
power = power * a % p;
ll tans = Cal(n,power);
ans += tans;
}
cout << ans << endl;
return 0;
}
```
新的配色挺好看
## 觉得我在瞎说?说的不对?方法不够简洁?看不懂?或者觉得我长得太丑?请在评论区提出qwq。