|
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 |
#include <iostream> #include <cstring> #include <math.h> #include <stdio.h> #include <vector> #define ull unsigned long long #define max(a,b) a>=b?a:b using namespace std; int ans[200]; int prime[1001]; vector<int> v; ull _MAX; void primegenerator() { double p=sqrt(1001); v.push_back(2); for(int i=3;i<p;i+=2) { if(prime[i]==0) for(int j=i*2;j<1001;j+=i) prime[j]=1; } for(int i=3;i<1001;i+=2) { if(prime[i]==0) v.push_back(i); } } int main() { string s; int _max=0; int t,cnt,num; int kase=1; _MAX = 1000000000; _MAX *=_MAX; primegenerator(); cout<<v.size()<<"\n"; cin>>t; while(t--) { cin>>s; cnt=0; num=0; _max=0; memset(ans,0,sizeof(ans)); for(int i=0;i<s.size();i++) { if(s[i]=='!') cnt++; else { num*=10; num+=(s[i]-'0'); } } //cout<<num<<" "<<cnt<<"\n"; cout<<"Case "<<kase++<<": "; while(num>1) { int tmp=num; int j=0; while(tmp>1) { if(tmp%v[j]==0) { tmp/=v[j]; ans[j]++; //_max=max(j,_max); } else j++; } num-=cnt; } ull res=1; int f=1; for(int i=0;i<v.size();i++) { if(ans[i]!=0) res*=(ans[i]+1); if(res>_MAX) { f=0; break; } } if(f==1) cout<<res<<"\n"; else cout<<"Infinity\n"; } return 0; } |