Cod sursa(job #1744271)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 19 august 2016 15:49:29
Problema Mins Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <cstdio>
using namespace std;
int f[10], k;
void descomp(int n){
    k = -1;
    int d;
    d = 2;
    while (d * d <= n && n > 1){
        if (n % d == 0){
            f[++k] = d;
            while (n % d == 0)
                n /= d;
        }
        d ++;
    }
    if (n > 1)
        f[++k] = n;
    k ++;
}
int fact(int x){
    int ans, ns, v, i, nr, prod;
    ans = x;
    ns = 1 << k;
    for (v = 1; v < ns; v ++){
        nr = 0;
        prod = 1;
        for (i = 0; i < k; i ++)
            if (v & (1 << i)){
                nr ++;
                prod = prod * f[i];
            }
        if (nr % 2 == 1)
            ans -= x / prod;
        else
            ans += x / prod;
    }
    return ans;
}
int main(){
    freopen("mins.in", "r", stdin);
    freopen("mins.out", "w", stdout);
    int n, m, x, y;
    scanf("%d%d", &m, &n);
    x = 0;
    for (y = 1; y < m; y ++){
        descomp(y);
        x += fact(n - 1);
    }
    printf("%d", x);
    return 0;
}