2721: [Violet 5]樱花|约数个数-白红宇

2721: [Violet 5]樱花|约数个数

阅读量：4953 次

发布时间：2019-06-12

本文共 1096 字，大约阅读时间需要 3 分钟。

先跪一发题目背景QAQ

显然

x,y>n!,然后能够设

y=n!+d

原式子能够化简成

x = n ! 2 d + n!

那么解的个数也就是

n!的因子个数，然后线性筛随便搞一搞

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #define N 1000008#define mod 1000000007using namespace std;int sc(){ int i=0,f=1; char c=getchar(); while(c>'9'||c<'0'){ if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar(); return i*f;}long long ans=1;int lo[N],low[N],a[N],prime[N],s[N],top;int sum[N],n;void pre(int n){ for(int i=2;i<=n;i++) { if(!a[i]) s[prime[++top]=low[i]=lo[i]=i]=1; for(int j=1;prime[j]*i<=n;j++) { a[i*prime[j]]=1; lo[i*prime[j]]=prime[j]; if(i%prime[j]==0) { low[i*prime[j]]=low[i]*prime[j]; s[i*prime[j]]=s[i]+1; break; } low[i*prime[j]]=prime[j]; s[i*prime[j]]=1; } }}int main(){ pre(n=sc()); for(int i=2;i<=n;i++) { int now=i; while(now!=1) sum[lo[now]]+=2*s[now],now/=low[now]; } for(int i=1;i<=n;i++) ans=ans*(sum[i]+1)%mod; cout<