题目链接
题意:给定一个n，求 g(n)g(n)=f(x1)+f(x2)...+f(xm) ,其中 xi是 n 的约数， f(n)是取(a，b)，a
f(x)=∑x?1a=0∑x?1b=0[x?a?b]=x2?∑x?1a=0∑x?1b=0[x∣a?b]=x2?∑x?1a=0∑x?1b=0[xgcd(x,a)∣agcd(x,a)?b]
这里b只能取x的倍数，所以公式可以化简为
=x2?∑x?1a=0xxgcd(x,a)=x2?∑x?1a=0gcd(x,a)==x2?∑d|xd?euler(x/d)
g(n)=∑x|nf(x)=∑x|nx2?∑d|xd?euler(x/d)=∑x|nx2?∑x|n∑d|xd?euler(xd)转化一下=∑x|nx2?∑d|n∑i|ndd?euler(i)=∑x|nx2?∑d|nd?∑i|ndeuler(i)根据一个性质：一个数的约数的欧拉函数和还为这个数原式可化简为=∑x|nx2?∑dnd?nd=∑x|nx2?∑d|nn=∑x|nx2?∑x|nx2?n?h(n)（其中h(n)是n约数的个数）
最后由于积性函数的性质
g(n)=∏i=1r(pai+1i)2?1p2i?1?n?∏i=1rai+1
#include
using namespace std;
#define maxn 100010
#define ull unsigned long long
bool vis[maxn];
int prime[maxn];
int tp=0;
void init(void) {
memset(vis,0,sizeof vis);
vis[1]=vis[0]=1;
for(int i=1;
i1) {
ss*=2;
ans*=(1+(ull)n*(ull)n);
}
//cout << ans << " " << ss << endl;
printf("%llu\n",ans-ss);
}
int main()
{
init();
int t,n;
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
sov(n);
}
return 0;
} 推荐阅读
- HDU 5528【2015长春现场赛 B】 Count a * b
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- [数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends
- 模板 poj2947 Widget Factory 高斯消元
- 【扩展欧几里得】练习题
- 扩展欧几里得【数论
- 数论|hdu 5322 Hope（分治+NTT）
- HDU 5528 Count a × b
- 线性同余方程组
- 数论|AtCoder Beginner Contest 156 C.Rally