Pagini recente » Cod sursa (job #3286440) | Diferente pentru info-oltenia-2018/individual intre reviziile 16 si 7 | Cod sursa (job #3033151) | Cod sursa (job #374546) | Cod sursa (job #33376)
Cod sursa(job #33376)
#include <cstdio>
#include <cmath>
#define FIN "chernel.in"
#define FOUT "chernel.out"
#define MAX 100010
#define PRIM_MAX 16000
#define MAXSIZE MAX/16+1
long prim[PRIM_MAX], nr, ans;
long N,M;
char v[MAXSIZE];
void ciur(long n) {
long i,j;
for (i=1; ((i*i)<<1) + (i<<1) <= n; i++)
if ( (v[i>>3] & (1<< (i&7)))==0 )
for (j=(i*i)<<1+(i<<1); (j<<1) + 1 <=n; j+=(i<<1) + 1)
v[i>>3] |= (1<<(i&7));
if ( M%2 )
prim[nr=0] = 2;
else
nr=-1;
for (i=1; (i<<1)+1<=n; ++i)
if ( ((v[i>>3] & (1<<(i&7))) ==0) && (M%((i<<1)+1)==0) ) {
prim[++nr] = (i<<1)+1;
}
}
long putere(long n, long x) { //la ce putere apare x [prim] in descompunerea lui n!
long lala=0, p=n;
while (p)
lala+= (p/=x);
return lala;
}
long pute[50][MAX]; // :P
void solve() {
long i,j,sv=M, pt, ok=0;
for (j=0; j<=nr; ++j)
for (i=1; i<=N; ++i)
pute[j][i]=pute[j][i-1]+putere(i,prim[j]);
for (j=0; j<=nr && sv>1; ++j)
for (pute[j][0]=0; sv%prim[j] == 0; pute[j][0]++, sv/=prim[j] );
for (i=1; i<=N/2; ++i) {
//elementul i de pe randul N este N!/ [ (N-i)! * i! ]
ok= 1;
for (j=0; j<=nr && ok; ++j) {
pt = pute[prim[j]][2];
// if ( pt>(putere(N,prim[j])-putere(N-i, prim[j])-putere(i,prim[j])) )
if ( pt>pute[j][N]-pute[j][i]-pute[j][N-i] )
ok=0;
}
/*
if ( sv>1 )
if ( putere(N,sv) - putere(N-i,sv) - putere(i,sv) <= 0 )
ok=0;*/
if ( ok ) ans++;
}
ans*=2;
if ( ! (N%2) && ok ) ans--;
}
void scoate_prim() {
long i;
printf("{");
for (i=0; i<nr; ++i)
printf("%ld,",prim[i]);
printf("%ld};", prim[nr]);
}
int main() {
freopen(FIN, "r", stdin);
scanf("%ld %ld", &N,&M);
fclose(stdin);
N--;ans=0;
ciur((long) sqrt((double)M));
// scoate_prim();
// printf("%ld", nr);
solve();
freopen(FOUT, "w", stdout);
printf("%ld\n", ans);
fclose(stdout);
return 0;
}