Codeforces #599 Div1 A. Tile Painting

微妙にやらかしてる回。
https://codeforces.com/contest/1242/problem/A

問題

N個のマスが並んでいる。
これらのマスに色を塗りたい。
距離が2以上かつNの約数である2マスの間は、同じ色を塗らなければならない。
最大で何色の色を塗れるか？

解法

素因数が2つ以上あれば1で、1つあればその値分になる。

ll N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<ll> V;
	ll g=0;
	for(i=2;1LL*i*i<=N;i++) {
		if(N%i==0) {
			g=__gcd(g,(ll)i);
			while(N%i==0) N/=i;
		}
	}
	if(N>1) g=__gcd(g,N);
	
	if(g==0) g=1;
	cout<<g<<endl;
	
}

まとめ

Div1Aにしてもちょっと簡単？