AtCoder ARC #190 : C - A^n - 1

解けず…。
https://atcoder.jp/contests/arc191/tasks/arc191_c

問題

正整数Nが与えられる。
以下を満たす整数対(A,M)があれば答えよ。

正整数nに対し、A^n-1で表される整数のうち、Mの倍数となるnの最小値がNである。

解法

(A,M)=(N+1,N^2)が解となる。
A^N-1は(N+1)進数でNがN個並んだ数字となる。
N*(N+1)^d % (N^2) = Nなので、N0000....をN^2で割った余りは常にN。
よってNを並べてN^2の倍数になるのは、NがN桁並んだ時であり、問題文の条件に合う。

int T;
ll N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		
		cout<<(N+1)<<" "<<N*N<<endl;
	}
}

まとめ

本番、(A,M)=(N+1,N)を思いついた後、N^2にすればいいことに思いが至らず…。