Cod sursa(job #3203803)

Utilizator ililogIlinca ililog Data 14 februarie 2024 17:41:37
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.67 kb
using namespace std;
#include<iostream>
#include<fstream>
#define NMAX 100005

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

long long n, m;
long long v[1000001];

int main() {    
    fin >> n >> m;
    n--, m--;
    if (n > m) swap(n,m);
    
    for (long long i = n; i>=1; i--) {
        long long nrperechi = (n/i) * (m/i); ///perechi care au pe i ca div comun
        
        for (int j = 2*i; j<=n; j+=i) {
            nrperechi -= v[j]; ///scad perechile care au pe k*i ca cmmdc
        }
        v[i] = nrperechi; ///nr perechi care au pe i ca cmmdc
    }
    
    fout << v[1]; ///nr perechi care au pe 1 ca cmmdc
    
    return 0;
}