Resistors in Parallel
吐槽一下，网上搜索的题解一上来都是找规律，对于我这种对数论不敏感的人来说，看这种题解太难受了，找规律不失为一种好做法，但是题解仅仅包括找规律又有什么意义呢？
定义
\[f[i] = \begin{cases}\infin & \text{如果 i 有平方因子, 即$\exist d, d\ge 2$，使得 $i$ 能够被 $d^2$ 整除} \\i & otherwise\end{cases}
\]
又定义
\[s[i] = \frac{1}{{\sum_{d|i}\frac{1}{f[d]}}}
\]
给定一个 \(n (n\le 10^{100})\)，求\(\min_{1\le i\le n} s[i]\)
如果 \(p\) 是一个质数，那么\(f[p] = p\) , \(s[p] = \frac{p}{p+1}\) , 又可以发现 \(s\) 是一个积性函数，当\(x,y\) 互质时，\(s(xy) = s(x)s(y)\) , （因为\(x,y\) 除了 1 之外没有公共因子，所以\(s(x)\) 和\(s(y)\) 相乘，分母会出现\(s(xy)\) 的所有分母）。
而积性函数又有一个性质：如果 \(x\) 表示为 \(x = \prod p_i^{c^i}\)， 那么\(s(x) = \prod s(p_i^{c_i})\) 。
然后思考\(s(p_i^{c_i})\) 的值，由于 \(p^2,p^3…p^c\) 都是具有平方因子的数字，所以：\(s(p^i) = \frac{p}{p+1}, \forall i \in [1,c]\) 。
然后我们思考如何解决这个题，对于任意一个 \(x\) 都有 \(s(x) = \prod s(p_i)\) 而且 \(s(p) \lt 1\) ，并且随着 \(p\) 增大 \(s(p)\) 严格递减，所以：
\[\min_{1\le i \le n} s(i) = \prod_{1\le i\le k} s(p_i),\quad \text{并且}\prod_{1\le i \le k}p_i \le n ,\quad \text{$p_i$ 表示从2开始的第$i$个质数}
\]
另外当 n 等于 1 时，答案为 1。
所以我们只需要从小到大枚举最多100个数字（因为 n 总共才100位），找到公式描述中的 k，计算答案即可，注意答案中要求输出最简分数，所以在约分可以用一点小技巧（代码中有所体现），当然也可以直接求gcd来化简，但是C++实现的高精度操作除法比较麻烦。
关于高精度模板：https://www.cnblogs.com/1625–H/p/11141106.html
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 100000 + 5;
int prime[N], m, v[N];
void init(int n){
for (int i = 2; i <= n;i++){
if(!v[i]){
prime[++m] = i;
}
for (int j = 1; j <= m && prime[j] <= n / i;j++){
v[i * prime[j]] = 1;
if(i % prime[j] == 0)
break;
}
}
}
struct BigInteger{
static const int BASE = 10000;
static const int WIDTH = 4;
vector<int> s;
BigInteger(ll num=0) { *this = num; }
BigInteger(string str) { *this = str; }
BigInteger(const BigInteger& t) { this->s = t.s; }
BigInteger operator = (ll num){
s.clear();
do{
s.push_back(num % BASE);
num /= BASE;
} while (num > 0);
return *this;
}
BigInteger operator = (string &str){
s.clear();
int x, len = (str.length() - 1) / WIDTH + 1;
for (int i = 0; i < len;i++){
int end = str.length() - i * WIDTH;
int start = max(0, end - WIDTH);
sscanf(str.substr(start, end - start).c_str(), "%d", &x);
s.push_back(x);
}
return *this;
}
bool cmp(vector<int> &A, vector<int> &B){
if(A.size() != B.size())
return A.size() < B.size();
for (int i = A.size() - 1; i >= 0;i--){
if(A[i] != B[i])
return A[i] < B[i];
}
return false;
}
bool operator < (BigInteger & b){
return cmp(s, b.s);
}
bool operator > (BigInteger & b){
return b < *this;
}
bool operator <= (BigInteger &b){
return !(b < *this);
}
bool operator >= (BigInteger &b){
return !(*this < b);
}
bool operator == (BigInteger &b){
return !(b < *this) && (*this < b);
}
vector<int> mul(vector<int>& A, int b);
BigInteger operator*(int& b);
};
ostream& operator << (ostream &out, const BigInteger & x){
out << x.s.back();
for (int i = x.s.size() - 2; i >= 0;i--){
char buf[20];
sprintf(buf, "%04d", x.s[i]);
for (int j = 0; j < strlen(buf);j++)
out << buf[j];
}
return out;
}
istream& operator>>(istream &in, BigInteger &x){
string s;
if(!(in>>s))
return in;
x = s;
return in;
}
vector<int> BigInteger::mul(vector<int>&A, int b){
vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || t;i++){
if(i < A.size())
t += A[i] * b;
C.push_back(t % BASE);
t /= BASE;
}
return C;
}
BigInteger BigInteger::operator*(int &b){
BigInteger c;
c.s = mul(s, b);
return c;
}
int down[N];
int main() {
init(100000);
int T;
scanf("%d", &T);
while(T--){
BigInteger n;
cin >> n;
BigInteger acc = 1;
int pos = 0;
while(acc * prime[pos + 1] <= n){
pos++;
acc = acc * prime[pos];
}
for (int i = 1; i <= pos;i++){
down[i] = prime[i] + 1;
}
BigInteger fz = 1, fm = 1;
for (int i = 1; i <= pos;i++){
int flag = 0;
for (int j = 1; j <= pos;j++){
if(down[j] % prime[i] == 0){
down[j] /= prime[i];
flag = 1;
break;
}
}
if(!flag)
fz = fz * prime[i];
}
for (int i = 1; i <= pos;i++)
fm = fm * down[i];
cout << fz << '/' << fm << endl;
}
return 0;
}
贴个 python代码
N = 100010
prime = [0 for i in range(N)]
down = [0 for i in range(N)]
v = [0 for i in range(N)]
m = 0
T = 0
T = int(input())
def init(n):
global m
for i in range(2, n+1):
if v[i] == 0 :
m = m + 1
prime[m] = i
for j in range(1, m+1) :
if i * prime[j] > n :
break
v[i * prime[j]] = 1
if i % prime[j] == 0 :
break
maxn = 100000
init(maxn)
while T :
T -= 1
n = int(input())
pos = 0
acc = 1
while acc * prime[pos+1] <= n :
pos = pos + 1
acc = acc * prime[pos]
for i in range(1, pos+1):
down[i] = prime[i] + 1
fz = 1
fm = 1
for i in range(1, pos+1):
flag = 0
for j in range(1, pos + 1):
if down[j] % prime[i] == 0 :
down[j] = down[j] // prime[i];
flag = 1
break
if flag == 0:
fz = fz * prime[i]
for i in range(1, pos+1):
fm = fm * down[i] print("%d/%d"%(fz,fm))
