Submission #19517

#	Time	Username	Problem	Language	Result	Execution time	Memory
19517		min050820	Σ (kriii4_P2)	C++14	100 / 100	21 ms	1720 KiB

P2

#include <iostream>
using namespace std;

const long long mod=1000000007;

// dp[n] = N ^ (2^n)
long long pow_dpTable[100];

long long pow(long long N,long long P){
    N%=mod;
    pow_dpTable[0]=N;
    long long mask=1;
    long long result=1;
    int i;
    for(i=1;mask <= P;i++){
        pow_dpTable[i]=(pow_dpTable[i-1] * pow_dpTable[i-1])%mod;
        mask<<=1;
    }
    mask=1;
    for(i=0;mask <= P;i++){
        if(P&mask){
            result = (result * pow_dpTable[i]) % mod;
        }
        mask<<=1;
    }

    return result;
}

long long answer=0;

int p;

long long gcd(long long a, long long b)
{
    while (b != 0)
    {
        a %= b;
        a ^= b;
        b ^= a;
        a ^= b;
    }

    return a;
}

long long getNum(long long S,long long U){
    // Side Num
    long long gcdOfSU=gcd(S,U);
    long long mS=S / gcdOfSU;
    long long mU=U / gcdOfSU;

    long long mmS=pow(mS,mod-2);

    long long ans=(mU * mmS) % mod;
    return ans;
}

int main()
{
    cin >> p;
    for(int i=0;i<p;i++){
        long long side,sumSide;
        cin >> side >> sumSide;
        answer = (answer + getNum(side,sumSide)) % mod;

    }

    cout << answer;
    return 0;
}

• Subtask 1: 100 / 100