首页 > itarticle > hdu

hdu

admin 11月 14, 2020 0

链接：http://acm.hdu.edu.cn/showproblem.php?pid=2462
思路：假设最终答案是n个8，运用等比数列求和公式可以得出t = $frac{8}{9}*(10^x - 1)$。
那么由t % n == 0可以得出：

两边同时除以d = gcd(8, 9n):

接下来两种方法都可以做了，一种是典型的exbsgs，套上板子就行。
第二种就是欧拉定理，首先在这里给出一个结论，最小的x一定是$phi(frac{9n}{d})$的因子，证明如下：
假设最小的$x_0$有:

我们可以得到:

即:

由于:

得到:

这样的$x_0$不是最小的，矛盾，所以一定是因子。
所以我们只用枚举因子，快速幂检验结果是否符合，并更新最小值即可。
两种方法都要注意一下，中间取模的时候可能会爆long long

代码：
欧拉定理

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 

using namespace std;

typedef long long ll;
typedef __int128 LL;
ll n;

ll (ll x){
    ll res = x;
    for(int i = 2; 1ll * i * i <= x; i++){
        if(x % i == 0){
            res -= res / i;
            while(x % i == 0) x /= i;
        }
    }
    if(x > 1) res -= res / x;
    return res;
}

ll pow_mod(ll q, ll w, ll mod){
    ll ret = 1;
    while(w){
        if(w & 1) ret = (LL)ret * q % mod;
        q = (LL)q * q % mod;
        w >>= 1;
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int kase = 0;
    while(cin >> n){
        if(!n) break;
        n *= 9;
        n /= __gcd(n, 8ll);
        ll x = euler(n);
        cout << "Case " << ++kase << ": ";
        ll res = 1e18;
        for(int i = 1; 1ll * i * i <= x; i++){
            if(x % i) continue;
            if(pow_mod(10, i, n) == 1){
                res = min(res, (ll)i);
            }
            if(pow_mod(10, x / i, n) == 1){
                res = min(res, (ll)x / i);
            }
        }
        if(res == 1e18) res = 0;
        cout << res << 'n';
    }
    return 0;
}

bsgs

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef __int128 LL;
unordered_map<ll, ll> mp;

ll pow_mod(ll q, ll w, ll mod){
    ll ret = 1;
    while(w){
        if(w & 1) ret = (LL)ret * q % mod;
        q = (LL)q * q % mod;
        w >>= 1;
    }
    return ret;
}

ll exbsgs(ll a, ll b, ll c){
    ll cnt = 0, d = 1, t;
    while((t = __gcd(a, c)) != 1){
        if(b % t) return 0;
        ++cnt, b /= t, c /= t, d = d * a / t % c;
        if(d == b) return cnt;
    }
    mp.clear();
    ll x = sqrt(c) + 1, tmp = b % c;
    for(int i = 0; i < x; i++)mp[tmp] = i, tmp = (LL)tmp * a % c;
    ll y = tmp = pow_mod(a, x, c);
    tmp = (LL)tmp * d % c;
    for(int i = 1; i <= x; i++){
        if(mp.count(tmp))return x * i - mp[tmp] + cnt;
        tmp = (LL)tmp * y % c;
    }
    return 0;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    ll x;
    int kase = 0;
    while(cin >> x){
        if(!x) break;
        x *= 9;
        ll g = __gcd(x, 8ll);
        x /= g;
        ll res = exbsgs(10, 1, x);
        cout << "Case " << ++kase << ": " << res << 'n';
    }
    return 0;
}

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能