Help in Sum of GCD of Tuples

general
, ,
1

Here is my code for the problem at E - Sum of gcd of Tuples (Hard) :-

    #include<bits/stdc++.h>
    using namespace std;

    #define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    #define rep(i,a,b) for(int i=a; i<b; i++)
    #define drep(i,a,b) for(int i=a; i>b; i--)
    #define inf 1e+18L
    #define mod 1000000007
    #define pb push_back
    #define vi vector<int>
    #define pii pair<int, int>
    #define ll long long 
    #define fi first
    #define se second
    const auto pi = 3.14159265359;
    const auto e = 2.718281828459;

    int numdigits(int x)
    {
        return floor(log10(x)) + 1;
    }

    int modpower(int x, int y)
    {
        int res = 1;
        x %= mod;
        if(x == 0) return 0;
        while(y > 0)
        {
            if(y&1) res = (res*x)%mod;
            y >>= 1;
            x = (x*x)%mod;
        }
        return res;
    }

    void solve()
    {
        int n, k;
        cin >> n >> k;
        vi dp(k+1, 0); //dp[i] is the number of sequences with gcd i
        drep(i,k,0)
        {
            int val = k/i;
            val = modpower(val, n);
            val %= mod;
            for(int j=2*i; j<=k; j+=i)
            {
                val -= dp[j];
            }
            dp[i] = val;
        }
        // for(auto k : dp) cout << k << " ";
        // cout << "\n";
        int ans = 0;
        rep(i,1,k+1)
        {
            int var = ((dp[i]%mod)*(i%mod))%mod;
            ans = ((ans%mod) + (var%mod))%mod;
            ans %= mod;
        }
        cout << ans << "\n";
    }

    int main()
    {
        FASTIO
        // int t;
        // cin >> t;
        // while(t--)
            solve();
        return 0;
    }

It works for the first two sample test cases given with the problem but gives the incorrect output for the last sample test case (i.e. 100000 100000). Can anyone please help me to figure out the flaw in the code?

2

@everule1 Please help.

3
3 Likes
4

Thanks a lot.