题解 CF919E 【Congruence Equation】

interestingLSY

2018-02-01 22:04:16

Solution

# 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。