Cod sursa(job #1550945)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 14 decembrie 2015 23:04:45
Problema Pairs Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<bits/stdc++.h>
using namespace std;

ifstream fin("porcjoc.in");
ofstream fout("porcjoc.out");

const int XMAX=500005;

int n,fr[XMAX],cnt[XMAX];
long long sol,sum;

int main()
{
    int i,j,x,y;
    long long gc,nr;
    fin>>n;
    for (i=1;i<=n;i++) {fin>>x>>y;sum+=y;fr[x]+=y;}
    //ciur
    for (i=2;i<XMAX;i+=2) cnt[i]++;
    for (i=3;i<XMAX;i+=2)
        if (!cnt[i])
            for (j=i;j<XMAX;j+=i) cnt[i]++;
    for (i=2;i*i<XMAX;i++)
        for (j=i*i;j<XMAX;j+=i*i)
            cnt[j]=-1;

    sum=sum*sum;sol=sum;
    for (i=2;i<XMAX;i++)
        if (cnt[i]>0)
        {
            nr=0;
            for (j=i;j<XMAX;j+=i)
                nr+=fr[j];

            if (cnt[i]&1) sol-=nr*nr;
            else sol+=nr*nr;
        }

    gc=__gcd(sol,sum);
    sol/=gc;sum/=gc;
    fout<<sol<<"/"<<sum<<"\n";
    return 0;
}