题解：AT_abc222_g [ABC222G] 222

high_sky · 2025-05-10 15:18:12 · 题解

AT_abc222_g [ABC222G] 222 题解分析

思路

题意转化

等价于求最小的 x 使得：

引理部分

引理 1：若 ax\equiv 0\pmod m，那么 x\equiv0\pmod {\frac m {\gcd(a,m)}}。

引理 2：若 \frac{x} b\equiv 0\pmod m，那么 x\equiv 0\pmod {bm}。

变换

不难用两个引理转换题意为：

其中 x 是最小满足条件的数，以及：

注意到欧拉定理：

所以：

我们假设 \varphi(M)=kx+b，其中 k,b 为整数。

则：

推导得：

由于：

故：

由于 x 是最小满足条件的，所以：

其中 k_2 为整数。

• 若 k_2=0，则 \varphi(M)=kx，得到 x\mid\varphi(M)。
• 若 k_2\ne0，则 \varphi(M)=(k+k_2)x，得到 x\mid\varphi(M)。

综上所述：

故我们可以暴力枚举 \varphi(M) 的因子求出最小满足条件的 x 即可，时间复杂度为 \mathcal{O}(\sqrt{\varphi(M)})。

引理推导

引理 1 推导：

设 d=\gcd(a,m)，则设 a=da',m=dm'。

有：

设 k 为正整数，有：

得到：

所以：

由于：

所以又有：

引理 2 推导：

跟上述差不多。

首先设 k 为正整数，可以得到：

然后就有：

所以：

代码

时间复杂度 \mathcal{O}(T\sqrt{\varphi(M)})，代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#include <vector>
#define int long long
#define N 100000001
#define M 5761457
using namespace std;
int T;
//bool vis[N];
//int prime[N],phi[N],cnt;
int qpow(int a,int b,int mod) {
    int res = 1;
    while(b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    } 
    return res;
}
//void init(int n) {
//  phi[1] = 1;
//  for (int i = 2;i <= n;i ++) {
//      if (!vis[i]) prime[++cnt] = i,phi[i] = i - 1;
//      for (int j = 1;j <= cnt && prime[j] * i <= n;j ++) {
//          vis[prime[j] * i] = 1;
//          if (i % prime[j] == 0) {
//              phi[i * prime[j]] = prime[j] * phi[i];
//              break;
//          }
//          phi[i * prime[j]] = phi[prime[j]] * phi[i];
//      }
//  }
////    cout << cnt << endl;
////    for (int i = 1;i <= cnt;i ++) cout << prime[i] << ' ';
//}
int get_euler(int x) {
    int res = x;
    for (int i = 2;i * i <= x;i ++)
        if (x % i == 0){
            while(x % i == 0) x /= i;
            res = res / i * (i - 1);
        }
    if (x > 1) res = res / x * (x - 1);
    return res;
}
signed main(){
    //int T;
    cin >> T;
    for (;T--;) {
        int x;
        scanf("%lld",&x);
        int mod = ((x & 1) ? x * 9 : x / 2 * 9),phi = get_euler(mod),res = phi + 1;
        for (int i = 1;i * i <= phi;i ++)
            if (phi % i == 0) {
//              cout << i << ' ' << qpow(10,i,mod) << endl;
                if (qpow(10,i,mod) == 1) res = min(res,i);
                if (qpow(10,phi / i,mod) == 1) res = min(res,phi / i);
            }
        if (res == phi + 1) puts("-1");
        else printf("%lld\n",res);
    }
    return 0;
}

感谢管理员的审核，最后一次更改了一些细节。