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;
}


全部评论

相关推荐

认真搞学习:28小登的建议,投算法岗不要写什么物理竞赛,互联网+,多写点项目,用什么算法做了什么。还有本科算法是不可能的开发你这个也没有项目啊
点赞 评论 收藏
分享
07-03 16:13
嘉应学院 Python
xiaolihuam...:很明显骗子,如果是hr直接约你面试了,哪用得着内推,如果是员工的话,你得多优秀,一线员工直接加你微信,
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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