一个很无聊的题目,要注意负数的存在和溢出的问题。地址:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1730
#include <stdio.h>
#include <math.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAX = 50000;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int prime[MAX];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int number[MAX];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int find ( int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
number[0] = number[1] = 1;
for ( int i=2; i<=n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
number[i] = 0;
}
for ( int j=2; j<=n; j++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for ( int z=j+j; z<=n; z+=j )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( ! number[z] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
number[z] = 1;
}
}
}
int p = 0;
for ( i=0; i<=n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( !number[i] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
prime[p++] = i;
}
}
return p;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int num[MAX];
int pre;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int f ( __int64 n, int len )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int l, r, mid;
int flag = 1;
int n2 = ( int )( sqrt ( (double)n ) ) + 1;
l = 0;
r = len - 1;
while ( l<=r )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
mid = ( l + r ) / 2;
if ( prime[mid] > n2 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
r = mid - 1;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
l = mid + 1;
}
}
for ( int i=0; i<=r; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( ! ( n % prime[i] ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
flag = 0;
while ( ! ( n % prime[i] ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
num[pre++] = prime[i];
n /= prime[i];
}
break;
}
}
if ( flag )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
num[pre++] = n;
n = 1;
}
return n;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int gdc ( int a, int b )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
if ( a == 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return b;
}
if ( b == 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
return a;
}
return gdc ( b, a % b );
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
__int64 n;
int flag;
int len = find ( MAX );
while ( scanf ( "%I64d", &n ) != EOF && n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
__int64 temp = n;
if ( n < 0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
n = -n;
flag = 1;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
flag = 0;
}
pre = 0;
while ( n != 1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
n = f ( n, len );
}
int ans = -1;
int count = 1;
for ( int i=0; i<pre-1; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( num[i] != num[i+1] )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( ans == -1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
ans = count;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
ans = gdc ( ans, count );
}
count = 1;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
count ++;
}
}
if ( ans == -1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
ans = count;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
ans = gdc ( ans, count );
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( flag )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if ( ( ans % 2) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf ( "%d\n", ans );
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
for ( ; ! (ans % 2); ans/=2 );
printf ( "%d\n", ans );
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
printf ( "%d\n", ans );
}
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)