专栏文章

题解：AT_abc222_g [ABC222G] 222

hhigh_sky
AT_abc222_g题解参与者 10已保存评论 13

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
13 条
当前快照
1 份
快照标识符
@mipcor9c
此快照首次捕获于
2025/12/03 09:50
3 个月前
此快照最后确认于
2025/12/03 09:50
3 个月前
查看原文

AT_abc222_g [ABC222G] 222 题解分析

思路

题意转化

等价于求最小的 xx 使得：
29(10x−1)≡0(modK)\frac 2 9(10^x-1)\equiv 0\pmod K

引理部分

引理 11：若 ax≡0(modm)ax\equiv 0\pmod m，那么 x≡0(modmgcd⁡(a,m))x\equiv0\pmod {\frac m {\gcd(a,m)}}。
引理 22：若 xb≡0(modm)\frac{x} b\equiv 0\pmod m，那么 x≡0(modbm)x\equiv 0\pmod {bm}。

变换

不难用两个引理转换题意为：
10x≡1(modM)10^x\equiv 1\pmod M
其中 xx 是最小满足条件的数，以及：
M={92KK≡0(mod2)9KK≡1(mod2)M=\left\{\begin{matrix} \frac 9 2K & K\equiv 0\pmod 2\\ 9K &K\equiv 1\pmod 2 \end{matrix}\right.
注意到欧拉定理：
aφ(m)≡1(modm)a^{\varphi(m)}\equiv 1\pmod m
所以：
10φ(M)≡1(modM)10^{\varphi(M)}\equiv 1\pmod M
我们假设 φ(M)=kx+b\varphi(M)=kx+b，其中 k,bk,b 为整数。
则：
10kx×10b≡1(modM)10^{kx}\times10^b\equiv1\pmod M
推导得：
(10x)k×10b≡1(modM)(10^x)^k\times10^b\equiv 1\pmod M
由于：
10x≡1(modM)10^x\equiv1\pmod M
故：
10b≡1(modM)10^b\equiv1\pmod M
由于 xx 是最小满足条件的，所以：
b=k2xb=k_2x
其中 k2k_2 为整数。
  • 若 k2=0k_2=0，则 φ(M)=kx\varphi(M)=kx，得到 x∣φ(M)x\mid\varphi(M)。
  • 若 k2≠0k_2\ne0，则 φ(M)=(k+k2)x\varphi(M)=(k+k_2)x，得到 x∣φ(M)x\mid\varphi(M)。
综上所述：
x∣φ(M)x\mid\varphi(M)
故我们可以暴力枚举 φ(M)\varphi(M) 的因子求出最小满足条件的 xx 即可，时间复杂度为 O(φ(M))\mathcal{O}(\sqrt{\varphi(M)})。

引理推导

引理 11 推导：
设 d=gcd⁡(a,m)d=\gcd(a,m)，则设 a=da′,m=dm′a=da',m=dm'。
有：
ax≡0(modm)⇒da′x≡0(moddm′)ax\equiv0\pmod m\Rightarrow da'x\equiv0\pmod {dm'}
设 kk 为正整数，有：
da′x=kdm′da'x=kdm'
得到：
a′x=km′a'x=km'
所以：
a′x≡0(modm′)a'x\equiv0\pmod {m'}
由于：
gcd⁡(a′,m′)=1\gcd(a',m')=1
所以又有：
x≡0(modm′)⇒x≡0(modmgcd⁡(a,m))x\equiv 0\pmod {m'}\Rightarrow x\equiv 0\pmod {\frac m{\gcd(a,m)}}
引理 22 推导：
跟上述差不多。
首先设 kk 为正整数，可以得到：
xb=km\frac x b=km
然后就有：
x=bkmx=bkm
所以：
x≡0(modbm)x\equiv 0\pmod {bm}

代码

时间复杂度 O(Tφ(M))\mathcal{O}(T\sqrt{\varphi(M)})，代码如下：
CPP
#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;
}
感谢管理员的审核，最后一次更改了一些细节。

评论

共 13 条评论，欢迎与作者交流。

正在加载评论...