1624：樱花

1624：樱花(一本通网站原题链接)

【分析】

　　一般不定方程的解多是质因数分析。比如2x+3y=100，那么y=2*(50-x)/3，显然y是偶数，50-x必然是3的倍数，两组解的x的差必然是3的倍数等。对本题先试着解一下：x=y*n!/(y-n!)=n!*[y/(y-n!)]，由此可得两点：y>n!、y-n!是y*n!的约数，为了方便令y=n!+t，则x=n!*n!/t+n!。显然x的取值个数就是n!*n!的约数个数。接下来就是回顾质因数分解定理了：任何一个大于1的正整数都能唯一分解为有限个质数的乘积。比如：120=2X2X2X3X5。其约数个数的计算方法为：每个质数在约数中出现的个数为0-分解出的个数。比如120可分解为3个2，1个3，1个5的乘积。那约数中可能包含的2的个数分别为0个、1个、2个、3个，共4种（比分解式中2的方次大1——有0个的嘛)，其他的一样。故约数个数为(3+1)*(1+1)*(1+1)=16个。若x=a1^n1*a2^n2*a3^n3*......*ak^nk，那么x的约数个数为(n1+1)*(n2+1)*(n3+1)*......*(nk+1)。

　　接下来就是如何找n!*n!的质因数分解。显然，这不可能暴力求解，连n!*n!本身等于多少都算不出来（除非使用高精度——显然也没必要用这玩意儿)。不过n!*n!与n!的质因数应该是一样的，只是个数多了一倍。所以，我们可以转而求n!的质因数个数就好。暴力不行，就筛选。先做一个1-n的质数表，然后找个数。用一个例子来说吧：求100！中7的方次。能出现7的方次，那这个数必然是7的倍数，100！中有7、14、21、28、......、98共14个，其他数不可能有7的方次，那7的方次是14吗？不是。因为49是7的平方，相当于两个7。14个只计算了一次。那再寻找7^2的倍数，2个，在计算7的倍数时也算了他们，只是每个数只计了一次，实际上他们应该记两次，再加一次就好，故7的方次应该是14+2=16。（如果n更大，可能还会有7^3的倍数，每一个应该记三次，前面记了2次，再记一次就好，7的更高方次一样，每升一次方就加一次，直到这个方次超出n)。于是，循着这个思路写出代码。

//1624：樱花 
#include<iostream>
using namespace std;
int const N=1e6+5,MOD=1e9+7;
int a[N],p[N],b[N],n,cnt,ans=1;
void spr()//构建一个质数表 
{
    for(int i=2;i<=n;i++)
    {
        if(!p[i])
        {
            p[i]=i;
            b[++cnt]=i;
        }
        for(int j=1;j<=cnt&&p[j]<=p[i]&&i<=n/b[j];j++)
        {
            p[i*b[j]]=b[j];
        }
    }
}int main(){
    cin>>n;
    spr();
    for(int i=1;i<=cnt;i++)
    {
        int bs=b[i];
        while(bs<=n)
        {
            for(int j=bs;j<=n;j+=bs)a[i]++;
            bs*=b[i];
        }
    }
    for(int i=1;i<=cnt;i++)
        ans=ans*(2*a[i]+1)%MOD;
    cout<<ans;
    return 0;
}

　　手动计算下n=10没有问题。但提交只有一个点正确，其他的答案错误。再次读题，注意到数据可能很大，要对1e9+7取余。那么在最后输出答案时的计算

ans=ans*(2*a[i]+1)%MOD;就有问题了：先乘时数值己然溢出，再取余也于事无补，所以得扩展ans的范围。改int ans为long long ans。得如下代码（中间也想了很久，准备求助，固而加了注释）

//1624：樱花 
#include<iostream>
using namespace std;
int const N=1e6+5,MOD=1e9+7;
long long ans=1,a[N],p[N],b[N],n,cnt;
void spr()//构建一个n以内的质数表 
{
    for(int i=2;i<=n;i++)
    {
        if(!p[i])//未被赋值标记即为质数 
            p[i]=i,b[++cnt]=i;//质数的最小质因数当然是自己 
        for(int j=1;j<=cnt&&p[j]<=p[i]&&i<=n/b[j];j++)
            p[i*b[j]]=b[j];//标记i*b[j]的最小质因数为b[j] 
    }
    return;
}
int main(){
    cin>>n;
    spr();//生成n以内的质数表 
    for(int i=1;i<=cnt;i++)//计算每个质数在n!中的方次 
    {
        int bs=b[i];//依次取出各个质数 
        while(bs<=n)
        {
            a[i]+=n/bs;
            /*计算n！中bs的倍数个数,每个倍数只记一次，如果是高次方的倍数，分多次计算
            比如16!中2的方次，首先所有2的倍数8个，所有4的倍数4个，8的倍数2个，
            16的倍数1个，那2的方次为8+4+2+1=15。这与2的奇数倍2 6 10 14共4个记4次，
            4的奇数倍2个，每个记2次，共4次，8的奇数倍1个记3次，16的倍数1个记4次，
            总计4+4+3+4=15效果一样*/ 
            bs*=b[i];
        }
    }
    for(int i=1;i<=cnt;i++)
        ans=ans*(2*a[i]+1),ans%=MOD;//x是n!*n!的约数，故需2倍 
    cout<<ans;
    return 0;
}

　　然而，提交后得66分，还有三个点不过。其间，其他老师也发来了他们的AC代码，也能看懂，思路和方法也大体一样，我还是想找到出错原因，所以继续努力寻找。

　　首先，我试着输入1000001，看了下，我的数组设置的1e6+5，这个应该不会越界，答案居然给了我一个负数，这让我有点高兴，找到错点，那离真相就不远了。接着我便输出所有的a[]的值（当然很多，只有慢慢找异常），期间前面的数都很大，但还没有超限的。中间出现了几个负数。接着跟踪所有与a[]相关的数据，找到了bs的值出现负数。bs是质数方次，为何会出现负数呢？只有一种可能：值溢出。原来，病灶在int bs。加上long long 收工。（写这段是希望能给像我一样陷入迷团的朋友提供些许线索）

【AC代码】

//1624：樱花
#include<iostream>
using namespace std;
int const N=1e6+5,MOD=1e9+7;
long long ans=1,a[N],p[N],b[N],n,cnt;
void spr()//构建一个n以内的质数表
{
    for(int i=2; i<=n; i++)
    {
        if(!p[i])//未被赋值标记即为质数
            p[i]=i,b[++cnt]=i;//质数的最小质因数当然是自己
        for(int j=1; j<=cnt&&p[j]<=p[i]&&i<=n/b[j]; j++)
            p[i*b[j]]=b[j];//标记i*b[j]的最小质因数为b[j]
    }
    return;
}
int main() {
    cin>>n;
    spr();//生成n以内的质数表
    for(int i=1; i<=cnt; i++) //计算每个质数在n!中的方次
    {
        long long bs=b[i];//依次取出各个质数
        while(bs<=n)a[i]+=n/bs,bs*=b[i];
    }
    /*计算n！中bs的倍数个数,每个倍数只记一次，如果是高次方的倍数，分多次计算
    比如16!中2的方次，首先所有2的倍数8个，所有4的倍数4个，8的倍数2个，
    16的倍数1个，那2的方次为8+4+2+1=15。这与2的奇数倍2 6 10 14共4个记4次，
    4的奇数倍2个，每个记2次，共4次，8的奇数倍1个记3次，16的倍数1个记4次，
    总计4+4+3+4=15效果一样*/
    for(int i=1; i<=cnt; i++)
        ans=ans*(2*a[i]+1),ans%=MOD;//x是n!*n!的约数，故需2倍
    cout<<ans;
    return 0;
}

如有不妥之处，欢迎评论，谢谢你的阅读！

1624：樱花

1624：樱花(一本通网站原题链接)

推荐阅读