P1445 [Violet] 樱花
题目
求关于x , y x,yx,y的方程1 x + 1 y = 1 n ! \dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{n!}x1+y1=n!1有多少个正整数解。
- 1 ≤ n ≤ 10 6 1 \le n \le 10^61≤n≤106。
思路
由于式子1 x + 1 y = 1 n ! \dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{n!}x1+y1=n!1是分式，不好处理，我们先把它转为整式。
由于x , y , n ! > 0 x,y,n!>0x,y,n!>0则:
y × n ! + x × n ! = x × y y \times n! + x\times n!=x \times yy×n!+x×n!=x×y
y × n ! = x × y − x × n ! y \times n!=x \times y - x \times n!y×n!=x×y−x×n!
y × n ! = x × ( y − n ! ) y \times n!=x \times (y - n!)y×n!=x×(y−n!)
因为y × n ! > 0 y \times n! > 0y×n!>0
所以x × ( y − n ! ) > 0 x \times (y - n!) > 0x×(y−n!)>0，即y > n ! y > n!y>n!
同理，x > n ! x > n!x>n!。
那我们不妨令x = n ! + g x = n! + gx=n!+g，y = n ! + f y = n! + fy=n!+f，g , f > 0 g,f > 0g,f>0。
把x = n ! + g x = n! + gx=n!+g，y = n ! + f y = n! + fy=n!+f代入:
n ! × ( x + y ) = x × y n! \times (x + y) = x \times yn!×(x+y)=x×y
n ! × ( n ! + g + n ! + f ) = ( n ! + g ) × ( n ! + f ) n! \times (n! + g + n! +f) = (n! + g) \times (n! + f)n!×(n!+g+n!+f)=(n!+g)×(n!+f)
2 × n ! 2 + g × n ! + f × n ! 2 \times n!^2 + g \times n! + f \times n!2×n!2+g×n!+f×n!
= g × n ! + f × n ! + g × f = g \times n! + f \times n! + g \times f=g×n!+f×n!+g×f
n ! 2 = g × f n!^2 = g \times fn!2=g×f
由于只要知道g , f g,fg,f，我们就能求出对应的x , y x,yx,y，而只要求出g gg，我们就能求出f ff，所以我们只用求有多少个g gg就行。
显然，g gg是n ! 2 n!^2n!2的因数，那g gg的个数就是n ! 2 n!^2n!2的因数个数，设n ! = p 1 a 1 × p 2 a 2 × ⋯ × p m a m n! = p_1^{a_1} \times p_2^{a_2} \times \dots \times p_m^{a_m}n!=p1a1×p2a2×⋯×pmam，其中p i p_ipi都是质数，a i a_iai都大于0 00，那么n ! 2 n!^2n!2就等于p 1 2 × a 1 × p 2 2 × a 2 × ⋯ × p m 2 × a m p_1^{2 \times a_1} \times p_2^{2 \times a_2} \times \dots \times p_m^{2 \times a_m}p12×a1×p22×a2×⋯×pm2×am，那g gg肯定是由一些p pp相乘得到的，我们枚举每个p i p_ipi在g gg中可能出现的次数，有选个不选两种情况，有可能出现的次数为0 00~2 × a i 2 \times a_i2×ai次，共2 × a i + 1 2 \times a_i + 12×ai+1种情况，根据乘法原理，g gg共有( 2 × a 1 + 1 ) × ( 2 × a 2 + 1 ) × ⋯ × ( 2 × a m + 1 ) (2 \times a_1 + 1) \times (2 \times a_2 + 1) \times \dots \times (2 \times a_m + 1)(2×a1+1)×(2×a2+1)×⋯×(2×am+1)个，我们现在的目标就变成了求出所有的a i a_iai。
由于n ≤ 10 6 n \le 10^6n≤106，那n ! n!n!会非常大，朴素的质因数分解为O ( n ) O(\sqrt{n})O(n)，肯定会超时，这时我们不妨换个角度，我们枚举所有的质数，然后暴力求其指数。
1 ≤ n ≤ 10 6 1 \le n \le 10^61≤n≤106，我们可以用线性筛来求出所有1 11到n nn的质数。
对于每个质数，显然，在1 11到n nn中有⌊ n p i ⌋ \lfloor\dfrac{n}{p_i}\rfloor⌊pin⌋个数至少包含一个p i p_ipi，但别忘了，一个数可能包含多个p i p_ipi，我们再看有多少个数至少包含两个p i p_ipi，显然有⌊ n p i 2 ⌋ \lfloor\dfrac{n}{p_i^2}\rfloor⌊pi2n⌋个，以此类推，有⌊ n p i k ⌋ \lfloor\dfrac{n}{p_i^k}\rfloor⌊pikn⌋个数至少包含k kk个p i p_ipi。因为10 6 10^6106以内的质数很少，而质数函数的增长较快，我们可以暴力枚举k kk，直到p i k p_i^kpik在1 11到n nn中一个数没有，因为没有数包含k kk个p i p_ipi，自然也没有数包含多于k kk个p i p_ipi。
时间复杂度约为O ( n ) O(n)O(n)。
Code
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintMAXN=1e6+7;constintmod=1e9+7;intn,ans=1;vector<int>val;bitset<MAXN>bit;voidinit(){bit.set(1);for(inti=2;i<=n;i++){if(!bit[i])val.push_back(i);for(autou:val){if(i*u>n)break;bit.set(i*u);if(i%u==0)break;}}return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cin>>n;init();for(autou:val){intv=u,num=0;while(1){if(v>n)break;num+=(n/v);v*=u;}ans*=(2*num+1);ans%=mod;}cout<<ans<<endl;return0;}
