关键词：

#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 1e7;
int gi()
{
    int x=0,w=1;char ch=getchar();
    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if (ch=='-') w=0,ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
}
int pri[N+5],tot,zhi[N+5],low[N+5];
ll h[N+5];
void Mobius()
{
    zhi[1]=h[1]=1;
    for (int i=2;i<=N;i++)
    {
        if (!zhi[i]) low[i]=pri[++tot]=i,h[i]=i-2;
        for (int j=1;j<=tot&&i*pri[j]<=N;j++)
        {
            zhi[i*pri[j]]=1;
            if (i%pri[j]==0)
            {
                low[i*pri[j]]=low[i]*pri[j];
                if (low[i]==i)
                    if (i==pri[j]) h[i*pri[j]]=h[i]*pri[j]+1;
                    else h[i*pri[j]]=h[i]*pri[j];
                else
                    h[i*pri[j]]=h[i/low[i]]*h[low[i]*pri[j]];
                break;
            }
            low[i*pri[j]]=pri[j];
            h[i*pri[j]]=h[i]*h[pri[j]];
        }
    }
    for (int i=2;i<=N;i++)
        h[i]+=h[i-1];
}
int main()
{
    Mobius();
    int T=gi();
    while (T--)
    {
        int n=gi(),i=1;
        ll ans=0;
        while (i<=n)
        {
            int j=n/(n/i);
            ans+=(h[j]-h[i-1])*(n/i)*(n/i);
            i=j+1;
        }
        printf("%lld
",ans);
    }
}

bzoj4804欧拉心算欧拉函数

...0^7输出按读入顺序输出答案。样例输入110样例输出136题解欧拉函数其中用到了这个推导很简单：由欧拉函数的定义，$sumlimits_{i=1}^ksumlimits_{j=1}^i[gcd(i,j)=1]=sumlimits_{i=1}^kv 查看详情

bzoj4804:欧拉心算欧拉筛(代码片段)

题意：求(sum_i=1^nsum_j=1^nphi(gcd(i,j)))题解：(sum_i==1^nsum_j=1^nsum_d=1^n[gcd(i,j)==d]*phi(d))(=sum_d=1^nphi(d)*sum_i=1^nsum_j=1^n[gcd(i,j)==d])(=sum_d=1^nphi(d)*sum 查看详情

[bzoj4804]欧拉心算

题面戳我题意：求[sum_{i=1}^{n}sum_{j=1}^{n}phi(gcd(i,j))]多组数据，(nle10^7)。solSBT单组数据(O(sqrtn))都是套路了，完整公式就不写了。最后要线性筛出来的积性函数长成这样[h(T)=sum_{d|T}mu(fracTd)phi(d)]这个要怎么筛？我这种小菜鸡就只会大... 查看详情

bzoj4805:欧拉函数求和

Description求(sum_{i=1}^nvarphi(i),nleqslant2 imes10^9)Solution杜教筛...见上篇...Code/**************************************************************Problem:4805User:BeiYuLanguage:C++Result:AcceptedTime 查看详情

bzoj4869相逢是问候（线段树，欧拉定理）

【BZOJ4869】相逢是问候（线段树，欧拉定理）题面BZOJ题解根据欧拉定理递归计算（类似上帝与集合的正确用法)所以我们可以用线段树维护区间最少的被更新的多少次如果超过了(varphi)的限制就不用再计算了如果需要计算就每次暴... 查看详情

[bzoj2818]欧拉函数

...lt;=x,y<=(n/p)范围内gcd(x,y)=1的对数，而这个对数就是类似欧拉函数的一个前缀和。#include<cstdio>#include<cstring>usingnamespacestd;co 查看详情

bzoj4805欧拉函数求和（杜教筛）

【BZOJ4805】欧拉函数求和（杜教筛）题面BZOJ题解好久没写过了正好看见了顺手切一下令[S(n)=sum_{i=1}^nvarphi(i)]设存在的某个积性函数(g(x))[(g*varphi)(i)=sum_{d|i}g(d)varphi(frac{i}{d})][sum_{i=1}^n(g*varphi(i))(i)][=sum_{i=1}^nsum 查看详情

bzoj4173--欧拉函数

 题解：http://blog.csdn.net/PoPoQQQ/article/details/46820313 代码：1#include<iostream>2#include<cstdio>3#include<cstring>4#include<algorithm>5#include<cmath>6usingnam 查看详情

bzoj4805:欧拉函数求和

好久没写杜教筛了练练手AC量刷起#include<bits/stdc++.h>#defineRGregister#defineILinline#defineFill(a,b)memset(a,b,sizeof(a))usingnamespacestd;typedeflonglongll;constint_(1e7+1);ILintInput(){RGintx=0,z=1;RGcharc 查看详情

bzoj4802欧拉函数

4802:欧拉函数Description已知N，求phi(N)Input正整数N。N<=10^18Output输出phi(N)SampleInput8SampleOutput4　　很明显，这样的题就是一道十分简单的入门题。只是N比较大，但输入和输出都还没有爆longlong。如果输入高精度数，那就很恶心了（... 查看详情

bzoj4805欧拉函数求和

题解：杜教筛问题：式子推的不熟#include<iostream>#include<cstdio>#include<cstring>#include<map>usingnamespacestd;typedeflonglongLint;intn;map<int,Lint>f;intcntprime;intprime[1000009];int 查看详情

[bzoj]4805:欧拉函数求和

解题思路类似莫比乌斯函数之和题目大意：求[1,n]内的欧拉函数$varphi$之和。（$n<=2*10^{9}$）思路：令$M(n)=sum_{i=1}^{n}varphi(i) $，题目所求即为$M(n)$。由于$sum_{d|n}varphi(d)=n$，所以$sum_{i=1}^{n}sum_{d|i}varphi(d)=frac{n(n+1)}{2}$令$ 查看详情

bzoj35603560:dzylovesmathv（欧拉函数）

3560:DZYLovesMathVTimeLimit: 10Sec  MemoryLimit: 256MBSubmit: 241  Solved: 133Description给定n个正整数a1,a2,…,an，求的值（答案模10^9+7）。Input第一行一个正整数n。接下来n行，每行一个正整数，分别为a1,a2, 查看详情

bzoj4805:欧拉函数求和(杜教筛)(代码片段)

4805:欧拉函数求和TimeLimit: 15Sec  MemoryLimit: 256MBSubmit: 614  Solved: 342[Submit][Status][Discuss]Description给出一个数字N，求sigma(phi(i)),1<=i<=N Input正整数N。N 查看详情

bzoj2226[spoj5971]lcmsum莫比乌斯反演（欧拉函数？）

【BZOJ2226】[Spoj5971]LCMSumDescriptionGivenn,calculatethesumLCM(1,n)+LCM(2,n)+..+LCM(n,n),whereLCM(i,n)denotestheLeastCommonMultipleoftheintegersiandn.InputThefirstlinecontainsTthenumberoftestcases.Eac 查看详情

bzoj4173数学欧拉函数神题

【BZOJ4173】数学Description Input 输入文件的第一行输入两个正整数。 Output 如题SampleInput56SampleOutput240HINT N,M<=10^15题解：STEP1：这步还是很容易的吧~毕竟原来的式子不太舒服。但是注意，最后一个式子的取值只能... 查看详情

bzoj3560dzylovesmathv欧拉函数

...llip;,an。输出仅一行答案。样例输入361015样例输出1595题解欧拉函数由于$varphi$是积性函数，所以可以单独考虑每个质因子的贡献。那么对于最终的$a=i_1i_2dotsi_n$，若其包含$p^c,c>0 查看详情

bzoj3813奇数国线段树+欧拉函数

【BZOJ3813】奇数国Description给定一个序列，每次改变一个位置的数，或是询问一段区间的数的乘积的phi值。每个数都可以表示成前60个质数的若干次方的乘积。SampleInput6013115013117013023SampleOutput1824366HINTx≤100000，当ai=0时0≤ci−bi... 查看详情