yukicoder No.300 平方数

「平方数⇔素因数分解した時の指数が全て偶数」なので、Xを素因数分解して、指数が奇数のものを掛けあわせれば良い
最悪でもX自身をかければ平方数になるので、Y≦X≦10^12

int main(){
	long x,y=1,i,p;
	scanf("%ld",&x);
	for(p=2;p*p<=x;p++)if(x%p==0){
		i=0;
		while(x%p==0){
			x/=p;
			i++;
		}
		if(i%2==1)y*=p;
	}
	printf("%ld",y);
	return 0;
}

Xを素因数分解した時の指数が全て1ならYとしてX自身を取るよりほかないので、「Xから平方因子を除いていく」という方法でも答えを得ることができる

int main(){
	long x,p;
	scanf("%ld",&x);
	for(p=2;p*p<=x;p++)while(x%(p*p)==0)x/=p*p;
	printf("%ld",x);
	return 0;
}

これを縮めて

long x,p=2;
main(){
	for(scanf("%ld",&x);x%(p*p)?x/++p/p:(x/=p*p););
	x=!printf("%ld",x);
}

85B

2017/08/12追記
よく考えたらそんな難しいことをしなくても、Xの最大の平方因子をn^2とするとX/(n^2)が答えなので、単純なfor文で書ける

long x,p=1e6;
main(){
	for(scanf("%ld",&x);x%(p*p);p--);
	printf("%ld",x/p/p);
}

74B

メモ

yukicoderでゆるふわgolf

yukicoder No.300 平方数