Cod sursa(job #1607664)

Utilizator refugiatBoni Daniel Stefan refugiat Data 21 februarie 2016 15:04:11
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <iostream>
#include <fstream>
#include <bitset>
using namespace std;
ifstream si("mins.in");
ofstream so("mins.out");
bitset<1005> erat;
int cont;
int nrpr[170];
void ciur()
{
    cont=1;
    nrpr[0]=2;
    int i,j,k;
    for(i=3;i<1005;i+=2)
    {
        if(!erat[i])
        {
            nrpr[cont]=i;
            k=i+i;
            ++cont;
            for(j=i+k;j<1005;j+=k)
                erat[j]=1;
        }
    }
}
int nrd,diviz[170];
int prod;
long long sol;
void backt(int a,int k,int lim,int s)
{
    if(k!=1)
    {
        sol+=s*(a/prod);
    }
    if(k>nrd)
        return;
    int i;
    for(i=lim;i<nrd;++i)
    {
        prod*=diviz[i];

        if(prod>a)
        {
            prod/=diviz[i];
            return;
        }
        backt(a,k+1,i,-s);
        prod/=diviz[i];
    }
}
int main()
{
    ciur();
    int n,m;
    si>>n>>m;
    --m;
    int a;
    int x,r;
    long long sum=0;
    for(x=1;x<n;++x)
    {
        r=x;
        nrd=0;
        for(a=0;nrpr[a]<x&&nrpr[a]<m;a++)
        {
            if(x%nrpr[a]==0)
            {
                diviz[nrd]=nrpr[a];
                nrd++;
                while(x%nrpr[a]==0)
                {
                    x/=nrpr[a];
                }
            }
        }
        if(x!=1)
        {
            diviz[nrd]=x;
            ++nrd;
        }
        sol=0;
        prod=1;
        backt(m,1,0,-1);
        x=r;
        sum+=m-sol;
    }
    so<<sum<<'\n';
    return 0;
}