Cod sursa(job #3203800)

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

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

int n, m;
int v[1000001];

int main() {    
    fin >> n >> m;
    n--, m--;
    if (n > m) swap(n,m);
    
    for (int i = n; i>=1; i--) {
        int nrperechi = (n/i) * (m/i); ///perechi care au pe i ca div comun
        
        for (int j = 2*i; j<=n; j++) {
            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;
}