gcd1

Code

#include <bits/stdc++.h>
#define int long long 
#define endl "\n"

using namespace std;

const int N = 1e6+5;
const int MOD = 1e9+7;

int n,g,a[N];

int pw(int a, int b) {
    if (b == 0)
        return 1;
    int tmp = pw(a, b/2)%MOD;
    tmp = (tmp*tmp)%MOD;
    if (b&1) {
        tmp = (tmp * (a%MOD))%MOD;
    }
    return tmp;
}

int get(int l, int r, int x) {
    r = r - (r%x);
    if (r < l) return 0;
    return (r-l)/x+1;
}

int cnt[N];

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin >> n >> g;
    int ans = 0;
    for (int i=n;i >= 1;i--) {
        int soluong = get(i, n, i);
        int sum = pw(2, soluong)-1+MOD;
        sum %= MOD;
        for (int j=2*i;j <= n;j+=i) {
            sum -= cnt[j];
            sum += MOD;
            sum %= MOD;
        }
        cnt[i] = sum;
    }
    // for (int i=1;i <= n;i++)
    //     cout << i << ' ';
    // cout << endl;
    // for (int i=1;i <= n;i++){
    //     cout << i << ' ' << cnt[i] << endl;
    // }
    cout << cnt[g];

    return 0;
}