Cod sursa(job #2289946)

Utilizator raduandreicaRadu Andreica raduandreica Data 25 noiembrie 2018 15:53:47
Problema Frac Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <iostream>
#include <fstream>
using namespace std;
long long n,N,i,i0,j=0,k,Euler,m,p,q,u[12],pas;
int catecopr(int x)
{
    int a,nr; a=0;
    for(i=1;i<x;i++)
    {
        nr=1;
        for(i0=0;i0<j;i0++) if(i%u[i0]==0) {nr=0; i0=j;}
        if(nr==1) a++;
    }
    return a;
}
int cautbin()
{
    int a;
    while(1)
    {
        a=catecopr(k);
        if(a==p)
        {
            while(p==catecopr(k)) k--;
            return k;
        }
        if(a>p) k=k-pas;
        if(a<p) k=k+pas;
        pas=(pas+1)/2;
    }
}
int main()
{
    ifstream fin("frac.in"); ofstream fout("frac.out");
    fin>>n>>m;
    Euler=n;k=n;N=n;
    for(i=2;n>1;i++) {if((n/i)*i==n) {while((n/i)*i==n) n=n/i; u[j]=i;j++;}}
    for(i=0;i<j;i++) Euler=(Euler/u[i])*(u[i]-1);
    p=m%Euler; q=m/Euler; pas=k/2;
    i=cautbin();
    fout<<q*N+i;
    return 0;
}