interestingLSY 的博客

interestingLSY 的博客

题解 CF919E 【Congruence Equation】

posted on 2018-02-01 22:04:16 | under 题解 |

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

代码

为了方便大家直接复制粘贴看代码,这里只放出关键部分

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。