1730.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"stdio.h"

inline void swap(_int64 &a,_int64 &b)
{a^=b;b^=a;a^=b;}

_int64 gcd(_int64 a,_int64 b)
{
while(a%b){a%=b;swap(a,b);}
return b;
}


int main()
{_int64 a,i,n,k,t,h;

while(1)
{scanf("%I64d",&a);
if(a==0)break;
if(a<0)t=-a;else t=a;

for(i=2,n=999999;t>1&&n>1&&i*i<=t+1;i++)
{if(t%i==0)
	{for(k=1,h=i;h<=t/i&&t%(h*i)==0;h*=i,k++); 
		if(n<99999)n=gcd(n,k);else n=k;
		t/=h;
		}

}
while(a<0&&n%2==0){for(i=2;i<n;i++)if(n%i==0)break; n/=i;}
if(n==999999||t!=1)n=1;
printf("%I64d\n",n);
}

return 0;
}