网站加载进度条,做安全平台网站,长沙做网站开发大概价格,江门网站推广设计分析#xff1a;这道题对于我这种蒟蒻来说还是很有难度啊。 思路非常巧妙#xff0c;既然不定方程要有有限个数解#xff0c;那么这个肯定会对解有所限制#xff0c;也就是本题中的正整数.这个时候我们要表示出方程中的一个根x,设z n!,那么xyz/(y-z),这样的话不能得到答案… 分析这道题对于我这种蒟蒻来说还是很有难度啊。 思路非常巧妙既然不定方程要有有限个数解那么这个肯定会对解有所限制也就是本题中的正整数.这个时候我们要表示出方程中的一个根x,设z n!,那么xyz/(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. #includeiostream
#includecstdio
#includecstring
#includequeue
#includecmathusing 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;
} 转载于:https://www.cnblogs.com/zbtrs/p/7390316.html
