文章

7

粉丝

387

获赞

7

访问

67.3k

头像
杜教筛求积性函数前缀和
P1495
发布于2021年1月16日 00:29
阅读数 6.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;
...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发