注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

bjfu-1110 最大公约数和  

2012-12-17 18:47:01|  分类: ACM-bjfu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

最大公约数和

时间限制(普通/Java):5000MS/15000MS          运行内存限制:65536KByte
总提交:25            测试通过:6

描述

已知n(1≤n≤2000000000),令g(n)=gcd(1,n)+ gcd(2,n)+…+ gcd(n,n),输出g(n)的值。gcd(a,b)表示a与b的最大公约数。 

输入

输入包含若干个数据,每行一个数n。
数据组数不超过50000 。

输出

对于每个输入的n,在一行内输出g(n)。

样例输入

2
6

样例输出

3
15

提示

请使用scanf和printf输入与输出。

数据比较多,容易超时!

————————————————————————————————————————————————

这题是poj 2480的一个翻版。

直接找的规律,打出前25个,然后寻找规律。规律如下,可以把所有的数分为以下三类:

 *  第一种情况:f(a*b)=f(a)*f(b),gcd(a,b)=1

 *  第二种情况:f(a)=2*a-1,a为质数

 *  第三种情况:f(a^r)=a^(r-1)*(r*(a-1)+a),a为质数

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

1

3

5

8

9

15

13

20

21

27

21

40

25

39

45

48

33

63

37

72

65

63

45

100

65

前面两条规律很容易就能发现,第三条规律这么推导:

从1到a^r-1的所有数,和a^r的最大公约数只能是1,a^1,a^2……a^r-1,

通过几个例子可以发现:

最大公约数为a^(r-k)的数字个数为(a-1)*a^(k-1)

所以最大公约数1,a^1,a^2,....,a^(r-1)数字与a^r最大公约数和为r*[(a-1)*a^(r-1)],
然后加上a^n,整理后结果就是f(a^r)=a^(r-1)*(r*(a-1)+a)

/*
* test1.cpp
*
* Created on: 2012-12-17
* Author: fudq
* bjfu-oj 1110
* 找规律,规律如下,可以把所有的数分为以下三类:
* 第一种情况:f(a*b)=f(a)*f(b),gcd(a,b)=1
* 第二种情况:f(a)=2*a-1,a为质数
* 第三种情况:f(a^r)=a^(r-1)*(r*(a-1)+a),a为质数
*/
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<iostream>
using namespace std;
#define M 44721
#define N 1000010
int pNum,prime[M];
bool f[M];

//这里为了提高效率,初始的时候把表打到100

int num=101;
__int64 t[N]={0,1,3,5,8,9,15,13,20,21,27,21,40,25,39,45,48,33,63,37,72,65,63,45,100,65,75,81,104,57,135,61,112,105,99,117,168,73,111,125,180,81,195,85,168,189,135,93,240,133,195,165,200,105,243,189,260,185,171,117,360,121,183,273,256,225,315,133,264,225,351,141,420,145,219,325,296,273,375,157,432,297,243,165,520,297,255,285,420,177,567,325,360,305,279,333,560,193,399,441,520};


void fun()
{
//用素数筛选法建立素数表,从1到44721,因为n最大20 0000 0000,到根号n即可

int i,j;
pNum=0;
memset(f,true,sizeof(f));
f[0]=f[1]=false;
for(i=2;i<=(int)sqrt(M);i++)
{
if(f[i])
{
for(j=i*i;j<M;j+=i)
f[j]=false;
}
}
for(i=2;i<M;i++)
if(f[i])
prime[pNum++]=i;
}

__int64 pow1(int a,int b)
{
//求a^b,因为数据比较大,用pow函数可以会有精度问题
int i;
__int64 s;
for(i=0,s=1;i<b;i++)
s*=a;
return s;
}

__int64 fun1(int a)
{
if(a<num)
return t[a];
int i,s_a,s_b,cnt;
cnt=-1;
for(i=0;prime[i]<=(int)sqrt(a);i++)
{
if(a%prime[i]==0)
{
a/=prime[i];
cnt=prime[i];
s_a=prime[i];s_b=1;
while(a%prime[i]==0)
{
cnt*=prime[i];
a/=prime[i];
s_b++;
}
break;
}
}
if(cnt==-1)//第二种情况
return (__int64)a*2-1;//注意int64的强制转换
if(a==1)//第三种情况
return pow1(s_a,s_b-1)*(s_b*(s_a-1)+s_a);
//第一种情况
return fun1(cnt)*fun1(a);
}

void fun2()
{
//把前1000000个打表记录,为了提高效率
for(;num<=999999;num++)
t[num]=fun1(num);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin1.txt","r",stdin);
freopen("testout1.txt","w",stdout);
#endif
int n;
fun();
fun2();
while(scanf("%d",&n)!=EOF)
printf("%I64d\n",fun1(n));
return 0;
}


  评论这张
 
阅读(144)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018