yukicoder : No.2011 Arbitrary Mod (Hidden)

ネタ問？
https://yukicoder.me/problems/no/2011

問題

をMで割った余りを考える。
nは100以上とする。Mを10^7以上10^18以下の範囲で任意に選べるとき、どんなaでも解が同じになるようにせよ。

解法

2^n=0 (mod φ(M))であれば、aによらず余りが1となる。
あとは(a^2-398)がMと素で、かつφ(M)が2^100の約数であればよい。
M=3*5*17*65537とすると、Mは10^7以上かつφ(M)が2*4*16*65536=2^21で条件を満たす。

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	ll M=3*5*17*65537;
	cout<<M<<endl;
	cout<<1<<endl;
}

まとめ

とはいえこれ自力でパッとでるかな…