首页 > 代码库 > 【洛谷】P1445 没占到1444的愤怒
【洛谷】P1445 没占到1444的愤怒
继续洛谷刷水日常,突然遇到一道不是很水的题目……
https://www.luogu.org/problem/show?pid=1445
题意:给定n(1<=n<=1000000),求方程1/x+1/y=1/n!的正整数解的个数。
思考了5min后,就去看题解了……
Qrc:这也太弱了……
【思路】
原方程可变形为:
xy/(x+y)=n!
xy-(x+y)n!=0,配方后,得:
(x-n!)(y-n!)=(n!)^2
所以求出(n!)^2的因数个数即可,又由于因数定理(正整数的因数个数等于其所有质因数幂次+1的乘积),只要求出其质因数及幂次即可
又:(n!)^2的每个质因数的幂次都是n!的质因数的2倍
同理,n!的质因数幂次是1~n每个数质因数幂次的“和”
所以对1~n中所有数求出质因数及幂次即可
先筛出1~n中所有的质数
再对每一个质数判断,1~n中,它作为质因数出现了几次?
下面贴上代码:
1 #include<cstdio>
2 const int M=1e9+7;
3 int n,primes[5000001],num=0,Ans=1;
4 bool isntprime[10000001]={1,1};
5 void prime1(){//线性筛法
6 for(int i=2;i<=n;++i){
7 if(!isntprime[i])primes[++num]=i;
8 for(int j=1;j<=num&&i*primes[j]<=n;++j){
9 isntprime[i*primes[j]]=1;
10 if(!(i%primes[j]))break;
11 }
12 }
13 }
14 int main(){
15 scanf("%d",&n);
16 prime1();
17 for(int i=1;i<=num;++i){
18 int prime=primes[i],c=0;
19 for(long long j=prime;j<=n;j*=prime)
20 c+=n/j;//必须对prime的若干次幂都进行一遍,这样不会漏掉包含其多次幂的数
21 Ans=1ll*Ans*(c*2+1)%M;
22 }
23 printf("%d",Ans);
24 return 0;
25 }
【洛谷】P1445 没占到1444的愤怒
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。