Buna!
Ma poate ajuta cineva la problema primXXL # 2332 de pe pb info?
Cerința
Se dau n numere naturale şi un număr natural k. Aflaţi câte dintre numerele date îl divid pe k! ( k factorial).
Date de intrare
Fișierul de intrare primxxl.in conține pe prima linie numerele n şi k, iar pe a doua linie n numere naturale nenule separate prin spații.
Date de ieșire
Fișierul de ieșire primxxl.out va conține pe prima linie numărul d, reprezentând numărul numerelor de pe a doua linie a fișierului de intrare care îl divid pe k!.
Restricții și precizări
1 ≤ n ≤ 10.000
1 ≤ k ≤ 1.000.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000
Exemplu
primxxl.in
3 5
20 3 14
primxxl.out
2
Explicație
Avem k!=5!=120, iar dintre numerele date 20 şi 3 îl divid pe 120, deci două numere.
Răspunsuri la întrebare
Răspuns:
#include <fstream>
#include <bitset>
#define N 1000000
using namespace std;
struct PRIME
{
int pr,exp;
};
PRIME prime[N];
bitset <N>a;
int pl;
int GasescPutereP(int K,int p)
{
int exp=0;
while(K)
K/=p,exp+=K;
return exp;
}
void Ciur(int K)
{
a[1]=1;
for(int d=2;d<=K;++d)
if(a[d]==0)
{
prime[++pl].pr=d;
prime[pl].exp=GasescPutereP(K,d);
int j=d+d;
while(j<=K)
a[j]=1,j+=d;
}
}
bool primeFactorsofK(int numar,int k)
{
int counta=0;
while(!(numar%2))
numar>>=1,++counta;
if(counta>prime[1].exp)
return false;
if(numar>1)
for(int i=2;i<=pl&&numar>1;++i)
{
if(numar%prime[i].pr==0)
{
counta=0;
while(numar%prime[i].pr==0)
numar=numar/prime[i].pr,++counta;
if(counta>prime[i].exp)
return false;
}
if(prime[i].pr*prime[i].pr>numar)
break;
}
if(numar==1)
return true;
else
if(numar<=k)
return true;
else
return false;
}
int main()
{
ifstream f("primxxl.in");
int n,k;
f>>n>>k;
Ciur(k);
int x,nr=0;
while(n--)
{
f>>x;
if(primeFactorsofK(x,k))
++nr;
}
f.close();
ofstream g("primxxl.out");
g<<nr;
g.close();
return 0;
}
Explicație: