首页 > 代码库 > 【bzoj2721】[Violet 5]樱花 数论
【bzoj2721】[Violet 5]樱花 数论
题目描述
.gif)
输入
.gif)
输出
.gif)
样例输入
2
样例输出
3
题解
数论
设1/x+1/y=1/m，那么xm+ym=xy，所以xy-xm-ym+m^2=m^2，所以(x-m)(y-m)=m^2.
所以解的数量就是m^2的约数个数。
所以只需要算出n!中每个素数的出现次数即可。
我们可以先快筛出1~n的素数，然后考虑每个素数出现的次数。
而p出现的次数为包含p^1的数的个数+包含p^2的数的个数+...+包含p^k的数的个数，我们可以迭代来求。
最后把它们乘2加1再乘到一起即可。
#include <cstdio>#include <algorithm>#define N 1000010using namespace std;int prime[N] , tot , cnt[N];bool np[N];int main(){ int n , i , j; long long ans = 1; scanf("%d" , &n); for(i = 2 ; i <= n ; i ++ ) { if(!np[i]) prime[++tot] = i; for(j = 1 ; j <= tot && i * prime[j] <= n ; j ++ ) { np[i * prime[j]] = 1; if(i % prime[j] == 0) break; } } for(i = 1 ; i <= tot ; i ++ ) { for(j = n ; j ; j /= prime[i]) cnt[i] += j / prime[i]; ans = ans * (2 * cnt[i] + 1) % 1000000007; } printf("%lld\n" , ans); return 0;}
【bzoj2721】[Violet 5]樱花 数论
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。