|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
#include <iostream> #include <cstring> #include <math.h> #include <stdio.h> #include <vector> #include <fstream> #define ull unsigned long long using namespace std; int factor[10001][1230]; int factorcount[10001][1230]; int prime[10001]; vector<int> v; ull _MAX; void primegenerator() { double p=sqrt(10001); v.push_back(2); for(int i=3;i<p;i+=2) { if(prime[i]==0) for(int j=i*i;j<10001;j+=i) prime[j]=1; } for(int i=3;i<10001;i+=2) { if(prime[i]==0) v.push_back(i); } } void factorize() { for(int i=2;i<10001;i++) { int tmp=i; int j=0; while(tmp>1) { if(tmp%v[j]==0) { factorcount[i][j]++; factor[i][j]++; tmp/=v[j]; j=-1; } j++; if(j==v.size()) break; } for(int k=0;k<1230;k++) factorcount[i][k]+=factorcount[i-1][k]; } } int main() { primegenerator(); factorize(); int t,m,n; int kase=0; cin>>t; while(t--) { cin>>m>>n; kase+=1; if(m<=1 || n<=0) { cout<<"Case "<<kase<<":\n"; cout<<"Impossible to divide\n"; continue; } int imposbl=0; double min_d=2e9; for(int i=0;i<1230;i++) { if(factor[m][i]>factorcount[n][i]) { imposbl=1; break; } else if(factor[m][i] && factorcount[n][i] && factorcount[n][i]/factor[m][i] <min_d) { min_d = factorcount[n][i]/factor[m][i]; } } cout<<"Case "<<kase<<":\n"; if(imposbl==1) { cout<<"Impossible to divide\n"; } else { cout<<min_d<<"\n"; } } return 0; } |