Cod sursa(job #867127)
Utilizator | Data | 29 ianuarie 2013 10:22:43 | |
---|---|---|---|
Problema | Principiul includerii si excluderii | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.67 kb |
#include <stdio.h>
int v[4194000],d,i,k;
int main(){
freopen("diviz.in","r",stdin);
freopen("diviz.out","w",stdout);
int a,b,s,m;
scanf("%d",&m);
for(k=1;k<=m;k++){
scanf("%d%d",&a,&b);
for(i=1;i<=a;i++)
v[i]=0;
s=a;
for(i=2;i*i<=b;i++){
if(b%i==0){
while(b%i==0){
b=b/i;
}
d=1;
while(i*d<=a){
v[i*d]=1;
d++;}
}
}
d=1;
if(b!=1)
while(b*d<=a){
v[b*d]=1;
d++;}
for(i=1;i<=a;i++)
if(v[i]==1)
s--;
printf("%d\n",s);
}
return 0;
}