Cod sursa(job #2457184)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 16 septembrie 2019 21:03:09
Problema Pascal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <iostream>
#include <fstream>
#include <vector>
 
using namespace std;
 
ifstream fin("pascal.in");
ofstream fout("pascal.out");
 
int n;
 
struct boi{
    int d, p, top;
    int f1, f2;
};

int ch[6] = {0, 0, 0, 1, 0, 2};
int churro[3][5000041];
void gchurro(int a)
{
    int p = a;
    while(p <= n){
        for(int i = p; i <= n; i += p){
            churro[ch[a]][i]++;
        }
        p *= a;
    }
}

void blitzchurro(int a, int p = 1)
{
    int c = ch[a];
    for(int i = 1; i < a; i++){
        for(int j = a; j <= p; j += a){
            if(j+i*p > n){
                return;
            }
            churro[c][j+i*p] = churro[c][j];
        }
    }
    churro[c][p*a]++;
    p *= a;
    blitzchurro(a, p);
}

int susta(int a, int d)
{
    int p = d, r = 0;
    while(p <= a){
        r += a/p;
        p *= d;
    }
    return r;
}

int susta_reloaded(int a, int d)
{
    int r = 0;
    while(a % d == 0){
        a /= d;
        r++;
    }
    return r;
}
 
vector<boi> bois;
void release_bois(int d)
{
    for(int i = 2; d > 1; i++){
        boi b;
        b.d = i;
        b.p = 0;
        while(d % i == 0){
            b.p++;
            d /= i;
        }
        if(b.p != 0){
            blitzchurro(b.d);
            b.top = susta(n, b.d);
            b.f1 = 0;
            b.f2 = b.top;
            bois.push_back(b);
        }
    }
}
 
int fact(int n, int st = 2)
{
    int r = 1;
    for(int i = st; i <= n; i++){
        r *= i;
    }
    return r;
}
 
int comb(int n, int k)
{
    return fact(n, k+1) / fact(n-k);
}
 
bool big_brain(int i, int bi)
{
    boi & b = bois[bi];
    int d = b.d;
    b.f1 += churro[ch[d]][i];
    b.f2 -= churro[ch[d]][n-i+1];
    int idk = b.top - (b.f1+b.f2);
    return idk >= b.p;
}
 
int main()
{
    int d;
    fin >> n >> d;
    release_bois(d);
 
    int sol = 0;
    int bs = bois.size();
    for(int i = 1; i <= n/2; i++){
        bool good = true;
        for(int j = 0; j < bs; j++){
            good &= big_brain(i, j);
        }
        if(good){
            if(n % 2 == 0 && i == n/2){
                sol += 1;
            }else{
                sol += 2;
            }
        }
    }
    fout << sol;
    return 0;
}