洛谷原创 P1445 樱花

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×yy × 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!yn!同理x n ! x n!xn!。那我们不妨令x n ! g x n! gxn!gy n ! f y n! fyn!fg , f 0 g,f 0g,f0。把x n ! g x n! gxn!gy n ! f y n! fyn!f代入:n ! × ( x y ) x × y n! \times (x y) x \times yn!×(xy)x×yn ! × ( n ! g n ! f ) ( n ! g ) × ( n ! f ) n! \times (n! g n! f) (n! g) \times (n! f)n!×(n!gn!f)(n!g)×(n!f)2 × n ! 2 g × n ! f × n ! 2 \times n!^2 g \times n! f \times n!2×n!2g×n!f×n! g × n ! f × n ! g × f g \times n! f \times n! g \times fg×n!f×n!g×fn ! 2 g × f n!^2 g \times fn!2g×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⌊pi​n​⌋个数至少包含一个p i p_ipi​但别忘了一个数可能包含多个p i p_ipi​我们再看有多少个数至少包含两个p i p_ipi​显然有⌊ n p i 2 ⌋ \lfloor\dfrac{n}{p_i^2}\rfloor⌊pi2​n​⌋个以此类推有⌊ n p i k ⌋ \lfloor\dfrac{n}{p_i^k}\rfloor⌊pik​n​⌋个数至少包含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#includebits/stdc.h#defineintlonglongusingnamespacestd;constintMAXN1e67;constintmod1e97;intn,ans1;vectorintval;bitsetMAXNbit;voidinit(){bit.set(1);for(inti2;in;i){if(!bit[i])val.push_back(i);for(autou:val){if(i*un)break;bit.set(i*u);if(i%u0)break;}}return;}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cinn;init();for(autou:val){intvu,num0;while(1){if(vn)break;num(n/v);v*u;}ans*(2*num1);ans%mod;}coutansendl;return0;}