[BZOJ2721] [Violet 5]樱花

题目描述

Description

Input

Output

Sample Input

2

Sample Output

3

HINT

题目分析

先%一发题面
考虑丢番图那题
看成就是原题了
因为过大 瓶颈在于不能直接求出的约数个数
先把问题化简:求的约数个数
因为:
所以:
所以:约数和个数为
然后我们来求
又因为里的所有质因子都是以内的素数
所以先快筛素数,再对于枚举以内的它的所有的倍数,然后暴力求出的所有数中,一共含有 的幂次是多少。
然后乘一起就是答案

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
long long ans=1;
int prime[2000000],v[2000000];
void work()
{
    for(int i=2;i<=1000005;i++)
    {
        if(v[i]==0) prime[++prime[0]]=i;
        for(int j=1;j<=prime[0]&&i*prime[j]<=1000005;j++)
        {
            v[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}
int c[5000000];
int main()
{
    scanf("%d",&n);
    work();
    for(int i=1;i<=prime[0];i++)
        for(int j=prime[i];j<=n;j+=prime[i])
            for(int k=j;k%prime[i]==0;k/=prime[i]) c[i]++;
    for(int i=1;i<=prime[0];i++) ans=ans*(c[i]<<1|1),ans%=1000000007;
    printf("%lld",ans);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注