链接：传送门
题外话：这套题作为队内训练赛，然后找规律找炸了，后来补题，发现大家都在用java或者python写，太难了，不会啊，只会C++的萌新躲在墙角瑟瑟发抖，写下了这个C++版本的解题报告
题意：说有n(10^100)个电阻器并联，选一个无平方因子的数，他的阻值是所有因子的倒数和的倒数，求这n个电阻值的最小电阻
思路：找规律
首先作为最小的值分别是
2 6 30 210 2310......
这些数怎么来的呢
2 3 5 7 11......求前缀积即可
也就是说我们在前缀积中找一个最大的小于等于n的数即可
那么如何求它的阻值
1 1/1 2-5 2/3 6-29 6/12 30-209 30/72 210-2309 210/576你会发现分子就是刚刚的前缀积，分母则是对应的质数+1的前缀积
所以我们预处理两个数组，一个分子up[i]=up[i-1]*prime[i];一个分母down[i]=down[i-1]*(prime[i]+1);
由于n是100为，当前缀积求到60的时候，up[60].size()>100,即可结束
以up数组为索引，去找到对应最小阻值的下标，取gcd即可
这里的gcd不使用辗转相除法，由于只有60个质因子，我们每次去取余这些质因子，如果是公约数，将其约掉即可
这题C语言使用到的大数模板有：大数与整数相乘，大数除整数，大数取模整数
AC代码如下：
#include<bits/stdc++.h> using namespace std; #define ll long long bool flag[1005];//标记数组 int Ans_p[1005],tot;//素数表，总素数个数，注意（Ans_p[tot]）内有素数 void eulgp(int n)//2~n 内的素数 { tot=0; //初始化 memset(flag,-1,sizeof(flag)); for(int i=2;i<=n;++i){ if(flag[i]) Ans_p[++tot]=i; //存入素数 for(int j=1;(j<=tot)&&(i*Ans_p[j]<=n);++j){ flag[i*Ans_p[j]]=0; if(i%Ans_p[j]==0) //避免重复赋0及时跳出 break; } } } string div(string a,int b) { string c; int len=a.length(),ans=0; char s; for(int i=0; i<len; i++){ ans=ans*10+a[i]-'0'; s=ans/b+'0'; ans%=b; c+=s; } int pos=0; while(pos<len && c[pos]=='0') pos++; if(pos==len) return "0"; return c.substr(pos); } string mul(string a,int b) { string c; char s; int len=a.length(),ok=0; for(int i=len-1; i>=0; i--){ int temp=(a[i]-'0')*b+ok; ok=temp/10; s=temp+'0'; c=s+c; } while(ok){ s=ok+'0'; c=s+c; ok/=10; } return c; } int MOD(string str,int mod) { int rem=0; for(int i=0; i<str.length(); i++){ rem=rem*10+str[i]-'0'; rem=rem%mod; } return rem; } string up[65],down[65]; int main() { eulgp(1000); up[0] = down[0] = "1"; for(int i=1;i<=60;i++){ up[i] = mul(up[i-1],Ans_p[i]); down[i] = mul(down[i-1],Ans_p[i]+1); } int t;scanf("%d",&t); while(t--){ string n; cin>>n; for(int i=1;;i++){ if(up[i].size()>n.size()||(up[i].size()==n.size()&&up[i]>n)){ string ansu=up[i-1],ansd=down[i-1]; for(int j=1;j<=60;j++){ if(!MOD(ansu,Ans_p[j])&&!MOD(ansd,Ans_p[j])) ansu=div(ansu,Ans_p[j]),ansd=div(ansd,Ans_p[j]); } cout<<ansu<<"/"<<ansd<<endl; break; } } } return 0; }
