Cod sursa(job #1744282)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 19 august 2016 15:59:09
Problema Mins Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <cstdio>
using namespace std;
bool ciur[1005];
int f[10], prime[1005], np, k;
void nr_prime(){
    int i, j;
    np = 1; prime[1] = 2;
    for (i = 3; i <= 1000; i += 2)
        if (!ciur[i]){
            prime[++np] = i;
            for (j = i * i; j <= 1000; j += 2 * i)
                ciur[j] = 1;
        }
}
void descomp(int n){
    k = -1;
    int d;
    d = 1;
    while (prime[d] * prime[d] <= n){
        if (n % prime[d] == 0){
            f[++k] = prime[d];
            while (n % prime[d] == 0)
                n /= prime[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, y;
    long long x;
    scanf("%d%d", &m, &n);
    x = 0;
    nr_prime();
    for (y = 1; y < m; y ++){
        descomp(y);
        x += fact(n - 1);
    }
    printf("%lld", x);
    return 0;
}