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