AtCoder ABC #222 (エクサウィザーズプログラミングコンテスト2021) : G - 222

Gまではなんとか解けたけど。
https://atcoder.jp/contests/abc222/tasks/abc222_g

問題

正整数Kが与えられる。
22....2がKの倍数となるような最小の桁数はいくつか。

解法

まず22....2を扱うのが面倒なので、11....1を扱うようにする。
求める最小の桁数において、22...2=nKと表現できるとする。

• Kが偶数(K=2K')の場合、22...2=2nK'なので、11....1=nK'。よって11....1がK'の倍数となる最小の桁数を求めれば、それは解と一致する。
• Kが奇数の場合、22...2がKの倍数なら11...1もKの倍数である。この時の桁数は解と一致する。

ということで、まずKが偶数なら2で割っておき、以後11....1がKの倍数となる最小の桁数を考えよう。
まず、Kが2または5の倍数であるとき、明らかに解なしである。
そうでない場合、求める桁数をnとすると(10^n-1)/9=mKと表現できることになるので、10^n≡1 (mod 9K)となる最小の正整数nを求める問題と置くことができる。nはφ(9K)の約数なので、約数を列挙して10^n≡1となる最小の値を答えよう。

int T;
int K;

ll modpow(ll a, ll n,ll mo) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

int ok(int p,int mo) {
	ll a=modpow(10,p,mo);
	return a==1;
}

int totient(int v) {
	int ret=v;
	for(int i=2;i*i<=v;i++) if(v%i==0) {
		ret=ret/i*(i-1);
		while(v%i==0) v/=i;
	}
	if(v>1) ret=ret/v*(v-1);
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>K;
		if(K%2==0) K/=2;
		
		if(K%2==0||K%5==0) {
			cout<<-1<<endl;
			continue;
		}
		
		int ret=1<<30;
		y=totient(9*K);
		for(x=1;x*x<=y;x++) if(y%x==0) {
			if(ok(x,9*K)) ret=min(ret,x);
			if(ok(y/x,9*K)) ret=min(ret,y/x);
		}
		if(ret==1<<30) ret=-1;
		cout<<ret<<endl;
		
	}
	
}

まとめ

なんか今回前半も時間かかったんだよな。