G. Spare Tire

容斥

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;


const int mod =1e9+7;
const int maxn = 1e6 + 10;
LL arr[maxn];
int p;

LL get(LL x, LL y)
{
    LL cnt = x / y;
    return (((y * y)%mod * (cnt * (cnt + 1) %mod * (2 * cnt + 1)%mod*166666668%mod)%mod)+(cnt*(cnt+1)/2)%mod*y%mod+mod)%mod;
}

void getp(LL m) {
    p = 0;
    for(int i = 2; i * i <= m; i++) {
        if(m % i == 0) {
            arr[p++] = i;
            while(m % i == 0)
                m /= i;
        }
    }
    if(m> 1) arr[p++] = m;
}

int main() {
    LL n,m;
    while(scanf("%lld%lld", &n,&m) != EOF) {
        if(n==1)
        {
            puts("2");
            continue;
        }
        getp(m);
        LL sum = n %mod * (n + 1) %mod * (2 * n + 1) %mod *166666668%mod + n*(n+1)/2%mod;
        sum%=mod;
        LL ans = 0;
        for(int i = 1; i < (1 << p); i++) { //状压
            LL res = 0, cnt = 1;
            for(int j = 0; j < p; j++) {
                if(i & (1 << j)) {
                    cnt *= arr[j];
                    res++;
                }
            }
            if(res & 1) ans += get(n, cnt); //容斥
            else ans -= get(n, cnt);
            ans = (ans+mod)%mod;
        }
        printf("%lld\n", (sum-ans+mod)%mod);
    }
    return 0;
}


全部评论

相关推荐

06-02 15:53
阳光学院 Java
点赞 评论 收藏
分享
Java抽象带篮子:简历怎么写可以看看我发的帖子,你的第一个是实习经历吗?那怎么写的是你的第一个练手项目呢?简历写的怎么样直接投小厂面试一下就知道了
没有实习经历,还有机会进...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务