文章
7
粉丝
387
获赞
7
访问
67.5k
类似于欧拉函数因子的phi值之和等于n,这里直接求即可
只需要知道x^3+3x^2+x在1到n的和为n(n+1)(n+1)(n+4)/4 然后结合逆元的知识即可完成
#include<cstdio>
typedef unsigned long long ll;
const int MAXN = 2000001;
const ll ha = 1333333;
const int mod = 1000000007;
const int inv_4 = 250000002;
int g[MAXN],p[MAXN],cut,pri[MAXN],tot,head[MAXN];
ll n,sum[MAXN];
//手写哈希
int hashcode(ll x) {return x % ha;}
struct data{int next;ll x,v;}e[MAXN];
bool vis[MAXN];
void add(int u,ll v,ll x) {
e[++cut].v=v;e[cut].x=x;e[cut].next=head[u];head[u]=cut;
}
void build() {
g[1] = 5;
for (int i = 2; i < MAXN; i++) {
g[i] += (i*(1ll * i*i%mod + 3 * i + 1) - g[1]) % mod;
if (g[i] >= mod)g[i] -= mod;
for (int j = (i << 1); j < MAXN; j += i) {
g[j] -= g[i];
if (g[j] < 0)g[j] += mod;
}
g[i] += g[i - 1];
if (g[i] >= mod)g[i] -= mod;
}
}
ll solve(ll x) {
if(x<MAXN) return g[x];
ll ans=0,k=x%ha,last;
...
登录后发布评论
暂无评论,来抢沙发