icpc2018-焦作-E Resistors in Parallel-数论+大数

http://codeforces.com/gym/102028/problem/E

定义n种电阻，阻值r[i]={ inf | i%d²==0 && d>1 ， i | else}

然后定义n种电阻集合，S[i]={ j | i%j==0} , 现在询问给定n找出一个集合Si,使得将Si内的电阻并联之后电阻值最小，输出最简分数格式。

　　考虑将一个数质因数分解后 x=p1^a1p2^a2...pn^an，由于题目中i%d^2==0时电阻是无穷大，1/ri 就是零了不必再考虑，也就是说只用考虑x的不同因子的数量和大小即可，当大小尽可能的小，数量尽可能的多时答案就尽量的大。我们就想办法构造一个不大于n的形如 2*3*5*....*p_max的数，那么答案就是∏(1+1/pi)。由于n的范围很大而我java已经忘光，手写了个大数水过。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<map>
  5 #include<set>
  6 #include<stack>
  7 #include<deque>
  8 #include<bitset>
  9 #include<unordered_map>
 10 #include<unordered_set>
 11 #include<queue>
 12 #include<cstdlib>
 13 #include<ctype.h>
 14 #include<ctime>
 15 #include<functional>
 16 #include<algorithm>
 17 #include<bits/stdc++.h>
 18 using namespace std;
 19 #define LL long long 
 20 #define pii pair<int,int>
 21 #define mp make_pair
 22 #define pb push_back
 23 #define fi first
 24 #define se second
 25 #define inf 0x3f3f3f3f
 26 #define debug puts("debug")
 27 #define mid ((L+R)>>1)
 28 #define lc (id<<1)
 29 #define rc (id<<1|1)
 30 const int maxn=10010;
 31 const int maxm=50050;
 32 const double PI=acos(-1.0);
 33 const double eps=1e-6;
 34 const LL mod=1e9+7;
 35 LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
 36 LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
 37 LL qpow(LL a,LL b,LL c){LL r=1; for(;b;b>>=1,a=a*a%c)if(b&1)r=r*a%c;return r;}
 38 struct Edge{int v,w,next;};
 39 
 40 template<class T>
 41 ostream & operator<<(ostream &out,vector<T>&v){
 42     for(auto x:v)cout<<x<<' ';
 43     return out;
 44 }
 45 void read(LL &n){
 46     n=0; char c=getchar();
 47     while(c<'0'||c>'9')c=getchar();
 48     while(c>='0'&&c<='9') n=(n<<3)+(n<<1)+(c-'0'),c=getchar();
 49 }
 50 
 51 
 52 const int MAX=270;
 53 vector<int>prime;
 54 bool is[10010];
 55 void init(){
 56     is[0]=is[1]=1;
 57     for(int i=2;i<=MAX;++i){
 58         if(!is[i])prime.pb(i);
 59         for(auto v:prime){
 60             if(i*v>MAX)break;
 61             is[i*v]=1;
 62             if(i%v==0)break;
 63         }
 64     }
 65 }
 66 struct Bign{
 67     int a[121];
 68     Bign(){memset(a,0,sizeof(a));}
 69     Bign(char *s){
 70         memset(a,0,sizeof(a));
 71     a[0]=strlen(s);
 72     for(int i=0;i<a[0];i++)a[a[0]-i]=s[i]-'0';
 73     }
 74     Bign &operator *(int x){
 75         for(int i=1;i<=a[0];++i)a[i]*=x;
 76         for(int i=1;i<=a[0];++i){
 77             if(a[i]>9){
 78             a[i+1]+=a[i]/10,a[i]%=10;
 79             if(a[a[0]+1]) a[0]++;
 80             }
 81         }
 82         return *this;
 83     }
 84     bool operator>(Bign &A){
 85         if(a[0]!=A.a[0]) return a[0]>A.a[0];
 86         for(int i=a[0];i>=1;--i){
 87             if(a[i]>A.a[i])return 1;
 88             else if(a[i]<A.a[i]) return 0;
 89         }
 90         return 0;
 91     }
 92 }AA;
 93 ostream &operator<<(ostream &out,Bign &A){
 94     for(int i=A.a[0];i>=1;--i)out<<A.a[i];
 95     return out;
 96 }    
 97 void AC(){
 98     
 99     char str[111],one[100]="1";
100     scanf("%s",str);
101     Bign A(str);
102     Bign B(one);
103     int n;
104     for(n=0;n<prime.size();++n){
105         //cout<<prime[n]<<' '<<B<<' '<<A<<' '<<(B>A)<<endl;
106         B=B*prime[n];
107         //cout<<"n="<<n<<endl;
108         if(B>A)break;
109     }
110     vector<LL>fz,fm;
111     fz.pb(1),fm.pb(1);
112     for(int i=0;i<n;++i){
113         //LL fz1=1+prime[i],fm1=prime[i];
114         //fz*=fz1,fm*=fm1;
115         fz.pb(1+prime[i]);
116         fm.pb(prime[i]);
117     }
118     for(int i=0;i<fz.size();++i){
119         for(int j=0;j<fm.size();++j){
120             LL gg=gcd(fz[i],fm[j]);
121             fz[i]/=gg,fm[j]/=gg;
122         }
123     }
124     Bign FZ(one),FM(one);
125     for(auto v:fz)FZ=FZ*v;
126     for(auto v:fm)FM=FM*v;
127     cout<<FM<<"/"<<FZ<<endl;
128     //printf("%lld/%lld
",fm,fz);
129 }
130 int main(){init();
131     int T;
132     cin>>T;
133     while(T--)AC();
134     return 0;
135 }