cUrSeD gCd1

Code

#include <bits/stdc++.h>
#define _i long long
#define __i     if
#define _ tmp
#define ___ ___
#define R return
#define __r R 0;
#define aaaa 1000005
#define mmb 1e9+7
#define hetcuu signed
#define ccc cin 
#define cccc cout
#define hieudeptrai main

using namespace std;

_i m = mmb;
_i n,g;
_i ______[aaaa];
_i ___(_i a, _i b) {
    __i (b == 0)
        R 1;
    _i _ = ___(a, b/2)%m;
    _ = (_*_)%m;
    __i (b&1) {
        _ = (_ * (a%m))%m;
    }
    R _;
}

_i ga(_i l, _i r, _i x) {
    r = r - (r%x);
    __i (r < l) R 0;
    R (r-l)/x+1;
}

hetcuu hieudeptrai() {
    ccc >> n >> g;
    _i ans = 0;
    for (_i i=n;i >= 1;i--) {
        _i c = ga(i, n, i);
        _i s = ___(2, c)-1+m;
        s %= m;
        for (_i j=i;j <= n;j+=i) {
            s -= ______[j];
            s += m;
            s %= m;
        }
        ______[i] = s;
    }
    cccc << ______[g];

    __r
}