Cod sursa(job #1971012)

Utilizator Marina23Oprea Marina Marina23 Data 19 aprilie 2017 19:19:41
Problema Mins Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream>
#include <math.h>
using namespace std;
bool Ciur[1000001];
int Vmax,Nrp,Prime[80000],i,Fact[80000],k,t,j,Nr,M,w;
long long int A,B,Prod,Sol,Val,aux,B1;
int main()
{
    ifstream fin("mins.in");
    ofstream fout("mins.out");

    Ciur[0]=1;
    Ciur[1]=1;
    Vmax=1000000;
    Nrp=0;
    for(i=2;i<=Vmax;i++)
        if(Ciur[i]==0)
        {
            for(j=i+i;j<=Vmax;j+=i)
                Ciur[j]=1;
            Nrp++;
            Prime[Nrp]=i;
        }//if
    M=1;
    for(i=1;i<=M;i++)
    {
        fin>>A>>B;
        A--;
        B--;
        if(A<B)
        {
            aux=A;
            A=B;
            B=aux;

        }
        k=1;
        t=0;
        B1=B;
       /* while(B>1)
        {
            k++;
            if(B%Prime[k]==0)
            {
                while(B%Prime[k]==0)
                    B=B/Prime[k];
                t++;
                Fact[t]=Prime[k];
            }//if
            if(Prime[k]>sqrt(B) and B>1)
            {
                t++;
                Fact[t]=B;
                B=1;
            }//if
        }//while*/
        while(Prime[k]<B) Fact[++t]=Prime[k++];
        B=B1;

        Val=1<<t;
        Sol=0;
        for(j=1;j<=Val-1;j++)
        {
            Nr=0;
            Prod=1;
            for(w=0;w<=t-1;w++)
                if(((1<<w)&j)!=0)
                {
                    Nr++;
                    Prod=Prod*Fact[w+1];
                }//if
            if(Nr%2==0)
                Nr=-1;
            else
                Nr=1;
            if(Prod!=1)
                Sol+=1LL*Nr*(A/Prod)*(B/Prod);
        }//for j
        fout<<A*B-Sol<<'\n';
    }//for i

    fin.close ();
    fout.close();
    return 0;
}