제출 #19359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
19359		ilbbke	Σ (kriii4_P2)	C++98	0 / 100	0 ms	1236 KiB

P2

#include<stdio.h>
#define M 1000000007

int m;
long long a[10005],b[10005];

long long back(int x,long long k){
    long long t;
    if(x==0) return 1;
    if(x==1) return k;
    if(x==2) return k*k;
    t=back(x/2,k);
    return x%2?t*t%M*k%M:t*t%M;
}

long long f(long long x,long long y){
    long long c;
    while(c!=0)
    {
        c=x%y;
        x=y;
        y=c;
    }
    return x;
}

int main()
{
    scanf("%d",&m);
    int i;
    long long x,y,s=0;
    for(i=1;i<=m;i++){
        scanf("%lld %lld",&b[i],&a[i]);
        x=f(a[i],b[i]);
        a[i]=a[i]/x; b[i]=b[i]/x;
    }
    x=b[1];
    for(i=2;i<=m;i++){
        y=x;
        x=y*b[i]/f(y,b[i]);
    }
    for(i=1;i<=m;i++) {
        a[i]=a[i]*(x/b[i]);
        s+=a[i];
    }
    y=back(M-2,x);
    printf("%d",s*y%M);
    return 0;
}

• Subtask 1: 0 / 100