Cod sursa(job #3220521)

Utilizator iusty64Iustin Epanu iusty64 Data 3 aprilie 2024 21:46:07
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>
#include <iostream>

using namespace std;
const int Vmax = 1000001;
int c, d;
bool bad[Vmax];
int cnt[Vmax];
int main(){
    ifstream fin("mins.in");
    ofstream fout("mins.out");
    fin>>c>>d;
    c--;
    d--;
    long long sol=0;
    long long p = 1LL*c*d;
    for(int k=2;k<=min(c, d);k++){
        if(cnt[k]==0){
            for(int j=k;j<=min(c, d);j+=k){
                cnt[j]++;
            }
            if(k<1000)
                for(int o=k*k;o<=min(c, d);o+=k*k){
                    bad[o]=1;
                }
        }
    }
    for(int k=2;k<=min(c, d);k++){
        if(k<100)
            cout<<sol<<" ";
        if(bad[k])
            continue;
        if(cnt[k]%2){
            sol+=(1LL*(c/k)*1LL*(d/k));
        }
        else{
            sol-=(1LL*(c/k)*1LL*(d/k));
        }
        
    }
    fout<<p-sol;
}