欧拉函数的应用
#include <stdio.h>
#include <math.h>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAX = 32000;
![](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) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.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 ( int 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;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
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=r; i>=0; 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 power ( int a, int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int sum = 1;
int count = a;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while ( n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( n & 1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
sum *= count;
}
n >>= 1;
count *= count;
}
return sum;
}
![](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) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int n;
int sum, count;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int len = find ( MAX );
while ( scanf ( "%d", &n ) != EOF && n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if ( n == 1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf ( "0\n" );
continue;
}
pre = 0;
while ( n > 1 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
n = f ( n, len );
}
count = 1;
sum = 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) {
sum *= (num[i]-1)*power ( num[i], count-1 );
count = 1;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
count ++;
}
}
sum *= (num[i]-1)*power ( num[i], count-1 );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf ( "%d\n", sum );
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
25 | 26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 1 | 2 | 3 | 4 | 5 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论
![](/images/xml.gif)
阅读排行榜
评论排行榜
|
|