bzoj2721 [Violet 5]櫻花

?

分析：這道題對于我這種蒟蒻來說還是很有難度啊。

???? 思路非常巧妙，既然不定方程要有有限個數解，那么這個肯定會對解有所限制，也就是本題中的正整數.這個時候我們要表示出方程中的一個根x,設z = n!,那么x=yz/(y-z),這樣的話不能得到答案，我們要得到的式子一定是分母只能有乘積的形式，并且同一個字母不能同時在分子分母中出現，因為我們就是利用正整數的整除性來求解的，可以看出x和y都大于z,所以我們設y = z + d,帶入,就消掉了y，可以得到x = z^2/d + z,因為x是正整數，所以z^2/d必須是整數，所以d是z^2的因子，那么我們只需要求出z^2有多少個約數就好了.

???? 求約數的個數要用到乘法原理和線性篩，z可以表示為p1^k1 * p2^k2 * p3^k3*...*pn^kn這種形式，每個質因數可以選1到ki個或不選，而約數就是由不同的質因子通過相乘組合起來的，所以約數的個數就等于(k1 + 1)*(k2 + 1)*...*(kn + 1),而我們要求z^2的因子個數，總不可能直接平方吧......可以發現每個質因子的次數擴大了兩倍，那么每個質因子就有2*ki + 1種選擇，和上面一樣直接乘法原理出答案.

???? 因為z = n!,所以枚舉1到n中的質數i的倍數，看i出現了幾次，就能得到ki.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>using namespace std;const int mod = 1000000007;int prime[1000010], tot, cnt[1000010],n;
bool vis[1000010];long long ans = 1;void init()
{for (int i = 2; i <= n; i++){if (!vis[i])prime[++tot] = i;for (int j = 1; j <= tot; j++){if (prime[j] * i > n)break;vis[prime[j] * i] = 1;if (i % prime[j] == 0)break;}}
}int main()
{scanf("%d", &n);init();for (int i = 1; i <= tot; i++)for (int j = prime[i]; j <= n; j += prime[i])for (int k = j; k % prime[i] == 0; k /= prime[i])cnt[i]++;for (int i = 1; i <= tot; i++)ans = (ans * 1LL * (cnt[i] * 2 + 1) % mod) % mod;printf("%lld\n", ans);return 0;
}

?

????

?