首页 > itarticle > 「codeforces

「codeforces

admin 12月 11, 2020 0

「CodeForces-919E」Congruence Equation

给定a,b,n,p，求关于n的方程n⋅a^n≡b(mod p)在[1,x]中整数解的数量

题解

对原式$k cdot a^k equiv b quad (textrm{mod};p)$，考虑消去指数。由费马小定理，对质数$p$，有$a^{(p-1)} equiv 1 quad (textrm{mod};p)$。

令$k=xcdot(p-1)+y$，则原式转化为

$$(xcdot(p-1)+y)cdot a^{xcdot(p-1)+y} equiv b quad (textrm{mod};p)$$

$$(xcdot(p-1)+y)cdot a^{y} equiv b quad (textrm{mod};p)$$

$$xcdot(p-1)+y equiv b cdot a^{-y}quad (textrm{mod} p)$$

$$xequiv y-b cdot a^{-y}quad (textrm{mod} p)$$

问题转化为求$xequiv y-b cdot a^{-y}quad (textrm{mod} p)$在$(xcdot(p-1)+y)∈[1,n]$中解的个数。

枚举$y∈[0,p-2]$，计算$x$的个数，其中若$x,y$均为0时$n=0$，需要减去。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 


using namespace std;

typedef long long ll;

ll a, b, n, p;

ll (ll a, ll n = p - 2)
{
    ll res = 1;
    for(; n; n >>= 1, (a *= a) %= p) if(n & 1) (res *= a) %= p;
    return res;
}

int main()
{
    cin >> a >> b >> p >> n;
    ll inva = inv(a), res = 0;
    for(int y = 0; y < p - 1; y ++)
    {
        
        ll x = (y - b + p) % p;
        if(y <= n && (n - y) / (p - 1) >= x)
        {
            res += ((n - y) / (p - 1) - x) / p + 1;
            if(x == 0 && y == 0) res --;
        }
        (b *= inva) %= p;
    }
    cout << res << endl;
    return 0;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能