题目链接：传送门
题目需求：
这题就是上一篇博客的变形。
题目解析：首先先求出与N互质的个数，即N的欧拉函数值，之后分解出N的因子来，求解方法如下。
证明：
要求有多少个 i 满足gcd(i, N) = d 如果gcd(i, N) = d，则gcd(i/d, N/d) = 1 由于i <= N，所以 i/d <= N/d，转化为求多少个不大于N/d的数与N/d互质，而这就是欧拉函数 所以有phi(N/d)个 i 满足gcd(i, N) = d，所以∑d*phi(N/d)即为答案。
我搜了大部分人的题解都是利用乘性函数做的，思想我附在代码下面，因为已A，我就不用他们那种方法了。
代码：（欧拉函数打表204ms)
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
using namespace std;
ll phi[100005];
ll f[10005];
ll sum,n,t,tt,i;
void init()
{
memset(phi,0,sizeof(phi));
phi[1]=1;
for(int i=2; i<=10000; i++)
{
if(!phi[i])
{
for(int j=i; j<=10000; j=j+i)
{
if(!phi[j]) phi[j]=j;
phi[j]-=phi[j]/i;
}
}
}
}
int main()
{
init();
while(scanf("%I64d",&n)!=EOF)
{
tt=0;
for(i=2; i*i<n; i++)
{
if(n%i==0)
{
f[tt++]=i;
f[tt++]=n/i;
}
}
if(i*i==n)
f[tt++]=i;
sort(f,f+tt);
if(tt==0)
{
tt=2*n-1;
printf("%I64d\n",tt);
continue;
}
t=n;
sum=n;
for(i=2; i*i<=t; i++)
{
if(t%i==0)
{
sum-=sum/i;
t/=i;
while(t%i==0)
t/=i;
}
}
if(t!=1)
sum-=sum/t;
sum+=n;
for(i=0; i<tt; i++)
{
if(n/f[i]>=10000)
{
ll temp=n/f[i];
ll cot=temp;
for(ll z=2; z*z<=temp; z++)
{
if(temp%z==0)
{
t/=z;
cot-=cot/z;
while(temp%z==0)
temp/=z;
}
}
if(temp!=1) cot-=cot/temp;
sum+=cot*f[i];
continue;
}
sum+=(phi[n/f[i]])*f[i];
}
printf("%I64d\n",sum);
}
return 0;
}下面推导没看懂。。。。。
积性函数：若任取互质的两个数m,n，都有f(m*n) = f(m)*f(n)，那么f就是积性函数
积性函数的和也是积性的，所以如果我们设所求答案是f(n) 则： f(n) = f(m1)*(m2) 其中，m1*m2 = n 且m1,m2互质！
经过因子分解，那种只要求到f(p^k)就可以利用积性把所有结果相乘得到最后答案。
还要一个结论： f(n) = sum(p * phi(n/p)) 这个结论比较好证明的。
而根据公式phi(p^i) = (p-1)*p^(i-1)可以求出，这样整个问题就解决了。
