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

时间：2021-07-31 13:30:03

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

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

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

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

　　

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<map>

 #include<set>

 #include<stack>

 #include<deque>

 #include<bitset>

 #include<unordered_map>

 #include<unordered_set>

 #include<queue>

 #include<cstdlib>

 #include<ctype.h>

 #include<ctime>

 #include<functional>

 #include<algorithm>

 #include<bits/stdc++.h>

 using namespace std;

 #define LL long long

 #define pii pair<int,int>

 #define mp make_pair

 #define pb push_back

 #define fi first

 #define se second

 #define inf 0x3f3f3f3f

 #define debug puts("debug")

 #define mid ((L+R)>>1)

 #define lc (id<<1)

 #define rc (id<<1|1)

 const int maxn=;

 const int maxm=;

 const double PI=acos(-1.0);

 const double eps=1e-;

 const LL mod=1e9+;

 LL gcd(LL a,LL b){return b==?a:gcd(b,a%b);}

 LL lcm(LL a,LL b){return a/gcd(a,b)*b;}

 LL qpow(LL a,LL b,LL c){LL r=; for(;b;b>>=,a=a*a%c)if(b&)r=r*a%c;return r;}

 struct Edge{int v,w,next;};

 template<class T>

 ostream & operator<<(ostream &out,vector<T>&v){

     for(auto x:v)cout<<x<<' ';

     return out;

 }

 void read(LL &n){

     n=; char c=getchar();

     while(c<''||c>'')c=getchar();

     while(c>=''&&c<='') n=(n<<)+(n<<)+(c-''),c=getchar();

 }

 const int MAX=;

 vector<int>prime;

 bool is[];

 void init(){

     is[]=is[]=;

     for(int i=;i<=MAX;++i){

         if(!is[i])prime.pb(i);

         for(auto v:prime){

             if(i*v>MAX)break;

             is[i*v]=;

             if(i%v==)break;

         }

     }

 }

 struct Bign{

     int a[];

     Bign(){memset(a,,sizeof(a));}

     Bign(char *s){

         memset(a,,sizeof(a));

     a[]=strlen(s);

     for(int i=;i<a[];i++)a[a[]-i]=s[i]-'';

     }

     Bign &operator *(int x){

         for(int i=;i<=a[];++i)a[i]*=x;

         for(int i=;i<=a[];++i){

             if(a[i]>){

             a[i+]+=a[i]/,a[i]%=;

             if(a[a[]+]) a[]++;

             }

         }

         return *this;

     }

     bool operator>(Bign &A){

         if(a[]!=A.a[]) return a[]>A.a[];

         for(int i=a[];i>=;--i){

             if(a[i]>A.a[i])return ;

             else if(a[i]<A.a[i]) return ;

         }

         return ;

     }

 }AA;

 ostream &operator<<(ostream &out,Bign &A){

     for(int i=A.a[];i>=;--i)out<<A.a[i];

     return out;

 }

 void AC(){

     char str[],one[]="";

     scanf("%s",str);

     Bign A(str);

     Bign B(one);

     int n;

     for(n=;n<prime.size();++n){

         //cout<<prime[n]<<' '<<B<<' '<<A<<' '<<(B>A)<<endl;

         B=B*prime[n];

         //cout<<"n="<<n<<endl;

         if(B>A)break;

     }

     vector<LL>fz,fm;

     fz.pb(),fm.pb();

     for(int i=;i<n;++i){

         //LL fz1=1+prime[i],fm1=prime[i];

         //fz*=fz1,fm*=fm1;

         fz.pb(+prime[i]);

         fm.pb(prime[i]);

     }

     for(int i=;i<fz.size();++i){

         for(int j=;j<fm.size();++j){

             LL gg=gcd(fz[i],fm[j]);

             fz[i]/=gg,fm[j]/=gg;

         }

     }

     Bign FZ(one),FM(one);

     for(auto v:fz)FZ=FZ*v;

     for(auto v:fm)FM=FM*v;

     cout<<FM<<"/"<<FZ<<endl;

     //printf("%lld/%lld\n",fm,fz);

 }

 int main(){init();

     int T;

     cin>>T;

     while(T--)AC();

     return ;

 }

相关文章