POJ 2480
传送门
题意就是求Σgcd(i,n)[1<=i<=n].首先我们知道,如果枚举的话肯定是会超时的.那么现在我们可以这么想.假设k=gcd(i,n).f1=i/k.f2=n/k;那么gcd(f1,f2)=1&f1<f2.看到这是不是想起什么.欧拉函数？对.就是它了.OK.我们再从头开始.现在,假设某个k|n.那么f2=n/k.则存在phi(f2)个数和n的gcd=k.这样的话,这题就好做了.我们只需要求Σk*phi(f2);其中k|n,f2=n/k;到了这一步之后,还有一点就是不能直接枚举所有的k.这样也是会超时的.我们只要筛出n的所有素因子,然后dfs就ok了.这里的素数只需要筛到2^16次就OK了.而且一个<=2^31的数的素因子的个数最多是10个.这样的话,dfs就会非常快了.下面是我的代码:
/
ID:klion26
LANG:C
TASK:POJ_2480 欧拉函数
/
#include
#include
#include
#include
int n;
int eular[46500];
int idx,prime[5200];
int num[20][2],total
__int64 ans
void init(int n)//n是需要求欧拉函数的最大值
{//结果存在eular数组中
int i,j
memset(eular,0,sizeof(eular));
eular[1]=1
idx=0
for(i=2i<=n;i++)
{
if(0 == eular[i])
{//i是素数
prime[idx]=i
idx++
for(j=ij<=n;j += i)//j从i到n
{
if(0 == eular[j])
eular[j]=j
eular[j] = eular[j]/i(i-1);
}
}
}
}
int get_eular(int n)
{
int ret
int i,k
if(n<46342)
return eular[n];
for(i=0i<idx;i++)
{
if(0 == (n%prime[i]))
break
}
if(i == idx)
return n-1
k = n/prime[i];
if(0 == (k%prime[i]))
ret = prime[i]get_eular(k);
else
ret = (prime[i]-1)get_eular(k);
return ret
}
void make(int n)
{
int i,j
total=0
for(i=0i<idx;i++)
{
if(0 == (n%prime[i]))
{
num[total][0]=prime[i];
j=0
while(0 == (n%prime[i]))
{
n /= prime[i];
j++
}
num[total][1]=j
total++
}
if(1 == n)
break
}
if(n>1)
{
num[total][0]=n;
num[total][1]=1
total++
}
return ;
}
void dfs(int now,int dep)
{
int i,j
if(dep==total)
{
i = get_eular(n/now);
ans += inow
return ;
}
j=1
for(i=0i<=num[dep][1];i++)
{
now = j
dfs(now,dep+1);
now /= j
j = num[dep][0];
}
}
void work(int n)
{
make(n);
ans=0
dfs(1,0);
printf(“%I64d\n“,ans);
}
int main(void)
{
init(46341);
while(EOF != scanf(“%d”,n))
work(n);
return 0
}
ID:klion26
LANG:C
TASK:POJ_2480 欧拉函数
/
#include
#include
#include
#include
int n;
int eular[46500];
int idx,prime[5200];
int num[20][2],total
__int64 ans
void init(int n)//n是需要求欧拉函数的最大值
{//结果存在eular数组中
int i,j
memset(eular,0,sizeof(eular));
eular[1]=1
idx=0
for(i=2i<=n;i++)
{
if(0 == eular[i])
{//i是素数
prime[idx]=i
idx++
for(j=ij<=n;j += i)//j从i到n
{
if(0 == eular[j])
eular[j]=j
eular[j] = eular[j]/i(i-1);
}
}
}
}
int get_eular(int n)
{
int ret
int i,k
if(n<46342)
return eular[n];
for(i=0i<idx;i++)
{
if(0 == (n%prime[i]))
break
}
if(i == idx)
return n-1
k = n/prime[i];
if(0 == (k%prime[i]))
ret = prime[i]get_eular(k);
else
ret = (prime[i]-1)get_eular(k);
return ret
}
void make(int n)
{
int i,j
total=0
for(i=0i<idx;i++)
{
if(0 == (n%prime[i]))
{
num[total][0]=prime[i];
j=0
while(0 == (n%prime[i]))
{
n /= prime[i];
j++
}
num[total][1]=j
total++
}
if(1 == n)
break
}
if(n>1)
{
num[total][0]=n;
num[total][1]=1
total++
}
return ;
}
void dfs(int now,int dep)
{
int i,j
if(dep==total)
{
i = get_eular(n/now);
ans += inow
return ;
}
j=1
for(i=0i<=num[dep][1];i++)
{
now = j
dfs(now,dep+1);
now /= j
j = num[dep][0];
}
}
void work(int n)
{
make(n);
ans=0
dfs(1,0);
printf(“%I64d\n“,ans);
}
int main(void)
{
init(46341);
while(EOF != scanf(“%d”,n))
work(n);
return 0
}
