BZOJ_4804_欧拉心算_欧拉函数
Description
给出一个数字N
Input
第一行为一个正整数T，表示数据组数。
接下来T行为询问，每行包含一个正整数N。
T<=5000,N<=10^7
Output
按读入顺序输出答案。
Sample Input
1
10
10
Sample Output
136
$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\varphi(gcd(i,j))$
$=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{p=1}^{n}\varphi(p)*[gcd(i,j)=p]$
$=\sum\limits_{p=1}^{n}\varphi(p)\sum\limits_{i=1}^{n/p}\sum\limits_{j=1}^{n/p}[gcd(i,j)=p]$
$=\sum\limits_{p=1}^{n}\varphi(p)f(n/p)$
其中$f(n)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[gcd(i,j)=1]=2*\varphi(n)-1$
然后根号处理即可。
代码：
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
int prime[10000050],cnt,phi[10000050];
ll s[10000050];
bool vis[10000050];
void init() {
int i,j;
phi[1]=s[1]=1;
for(i=2;i<=10000000;i++) {
if(!vis[i]) {
prime[++cnt]=i; phi[i]=i-1;
}
for(j=1;j<=cnt&&i*prime[j]<=10000000;j++) {
vis[i*prime[j]]=1;
if(i%prime[j]==0) {
phi[i*prime[j]]=phi[i]*prime[j]; break;
}
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
s[i]=s[i-1]+phi[i];
}
}
ll calc(int n) {
int i,lst;
ll ans=0;
for(i=1;i<=n;i=lst+1) {
lst=n/(n/i);
ans+=(s[lst]-s[i-1])*(2*s[n/i]-1);
}
return ans;
}
int main() {
init();
int T;
scanf("%d",&T);
int n;
while(T--) {
scanf("%d",&n);
printf("%lld\n",calc(n));
}
}