【洛谷P1445】[Violet]櫻花【數論】

l i n k link link

分析：

推式子

1 x + 1 y = 1 n ! \frac{1}{x}+\frac{1}{y}=\frac{1}{n!} x1​+y1​=n!1​

先通分

x + y x y = 1 n ! \frac{x+y}{xy}=\frac{1}{n!} xyx+y​=n!1​

交叉相乘

x y = n ! ( x + y ) xy=n!(x+y) xy=n!(x+y)

移項

− n ! ( x + y ) + x y = 0 -n!(x+y)+xy=0 −n!(x+y)+xy=0

兩邊加上 ( n ! ) 2 (n!)^2 (n!)2

( n ! ) 2 − n ! ( x + y ) + x y = ( n ! ) 2 (n!)^2-n!(x+y)+xy=(n!)^2 (n!)2−n!(x+y)+xy=(n!)2

因為友善十字相乘法 因式分解

( n ! − x ) ( n ! − y ) = ( n ! ) 2 (n!-x)(n!-y)=(n!)^2 (n!−x)(n!−y)=(n!)2

令 a = ( n ! − x ) a=(n!-x) a=(n!−x) b = ( n ! − y ) b=(n!-y) b=(n!−y)

因為 ( n ! ) 2 (n!)^2 (n!)2已确定 那隻要确定 a a a 就能确定 b b b 也就能确定 x x x和 y y y

a a a是 ( n ! ) 2 (n!)^2 (n!)2的因子 那 a a a的方案數 就是 ( n ! ) 2 (n!)^2 (n!)2因子的方案數

然後唯一分解定理：

n ! = p 1 c 1 + p 2 c 2 + p 3 c 3 + . . . + p m c m n!=p_1^{c_1}+p_2^{c_2}+p_3^{c_3}+...+p_m^{c_m} n!=p1c1​​+p2c2​​+p3c3​​+...+pmcm​​

( n ! ) 2 = p 1 c 1 × 2 + p 2 c 2 × 2 + p 3 c 3 × 2 + . . . + p m c m × 2 (n!)^2=p_1^{c_1\times2}+p_2^{c_2\times2}+p_3^{c_3\times2}+...+p_m^{c_m\times2} (n!)2=p1c1​×2​+p2c2​×2​+p3c3​×2​+...+pmcm​×2​

每個質因子 p i p_i pi​都有 2 × c i + 1 2\times c_i+1 2×ci​+1種取值

a n s = ( c 1 × 2 + 1 ) × ( c 2 × 2 + 1 ) × ( c 3 × 2 + 1 ) × . . . × ( c m × 2 + 1 ) ans=(c_1\times2+1)\times(c_2\times2+1)\times(c_3\times2+1)\times...\times(c_m\times2+1) ans=(c1​×2+1)×(c2​×2+1)×(c3​×2+1)×...×(cm​×2+1)

最後線性篩出質數 然後把指數 c i c_i ci​累計完求 a n s ans ans

CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1e6+5,mod=1e9+7;
ll n,cnt,ans=1,num[N],prime[N],c[N];
int main()
{
	scanf("%lld",&n);
	for(int i=2;i<=n;i++)
	{
		if(!num[i]){
			num[i]=i;
			prime[++cnt]=i;
		}
		for(int j=1;j<=cnt&&i*prime[j]<=n;j++)
		{
			num[i*prime[j]]=prime[j];
			if(i%prime[j]==0) break;
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=i;j!=1;j/=num[j]) 
			c[num[j]]++;
	for(int i=1;i<=n;i++)
		ans=ans*(c[i]<<1|1)%mod;  //c[i]*2+1
	printf("%lld",ans);
	
	return 0;
}