容斥原理,先把 n 质分解,利用x^4 的前n项和公式,然后把与 n 不互质的数的和求出来然后减一下就可以了。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#define LL long long
#define CLR(a, b) memset(a, b, sizeof(a))
using namespace std;
const int N = 100000001;
const int M = 11111;
const int MOD = 1e9 + 7;
vector<LL> hav;
bool isp[M];
int p[M], cnt, sz;
LL n;
void getp()
{
CLR(isp, 0);
int i, j;cnt = 0;
isp[0] = isp[1] = 1;
for(i = 2; i < M; i ++)
{
if(!isp[i])
{
p[cnt ++] = i;
if(i <= 1111)for(j = i * i; j < M; j += i) isp[j] = 1;
}
}
}
void get_hav(LL h)
{
LL i;
hav.clear();
for(i = 0; i < cnt && h > 1; i ++)
{
if(h % p[i] == 0)
{
h /= p[i];
int s = hav.size();
if( s == 0 || hav[s - 1] != p[i])hav.push_back(p[i]);
i --;
}
}
if(h != 1) hav.push_back(h);
}
LL inv(LL x)
{
LL r, y;
for(r = 1, y = MOD - 2; y; x = x * x % MOD, y >>= 1) (y & 1) && (r = r * x % MOD);
return r;
}
LL get_sum(LL n)
{
LL ret;
ret = n * (2 * n + 1) % MOD * (n + 1) % MOD * ((3 * n * (n + 1) - 1) % MOD) % MOD * inv(30) % MOD;
return ret;
}
LL F_pow(LL a, LL b)
{
LL ret = 1;
while(b)
{
if(b & 1) ret = ret * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return ret;
}
LL dfs(LL u, LL c)
{
LL i, j;
LL ret = 0;
for(i = u; i < sz; i ++)
{
ret = (ret + F_pow(hav[i] * c, 4) * get_sum(n / hav[i] / c) % MOD - dfs(i + 1, c * hav[i])) % MOD;
}
return (ret + MOD) % MOD;
}
int main()
{
//freopen("input.txt", "r", stdin);
LL i, j, t;
getp();
cin >> t;
while(t --)
{
cin >> n;
get_hav(n);
sz = hav.size();
cout << (get_sum(n) - dfs(0, 1) + MOD) % MOD << endl;
}
}
分享到:
相关推荐
hdu 1695 GCD(欧拉函数+容斥原理).docx
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
有题,有解题思路,有解题代码 hdu2516、poj1067和hdu1527、hdu2177、hdu2176等等
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
华为HLR相关资料,介绍了HLR中的HDU数据库单元原理
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1166线段树代码
ACM HDU题目分类,我自己总结的大概只有十来个吧
自己做的HDU ACM已经AC的题目
HDU最全ac代码
hdu动态规划算法集锦
hdu 期末考试复习资料 计算机网络 编译原理 计算机图形学 编译原理 信息安全与技术 数据库应用系统开发