文章目錄

• 題目描述
• 解析
• 代碼

題目描述

數(shù)據(jù)范圍有誤！應(yīng)該是不超過1e6

解析

容易推出：

y=（x$?$n!)/(x-n!)

換元，令t=x-n！
則：

y=n!+(n!)²/t

因為x、y都與t一一對應(yīng)
所以本題就是求 (n!)² 的因數(shù)個數(shù)
我們求出n！的質(zhì)因數(shù)分解的話，問題就好辦了
問題在于怎么求
我們可以在預(yù)處理出[1,n]的素數(shù)表后，使用類似篩法的操作

for (int i = 1; i <= tot; i++) {for (ll j = prime[i]; j <= n; j *= prime[i]) {c[i] += n / j;c[i] %= mod;}}

為什么可以這樣
我們舉個例子
當(dāng)n=27,模數(shù)為3時
我們就是要求橫線出現(xiàn)的次數(shù)
回去看代碼
j的每一層循環(huán)其實就是在算某一層的線段個數(shù)
最后加在一起
還是挺巧妙的

代碼

#include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e7+100; const int M=1e7+100; const int mod=1e9+7; ll n; int prime[N],v[N],tot,c[N]; void findprime(){for(int i=2;i<=n;i++){if(!v[i]){v[i]=i;prime[++tot]=i;}for(int j=1;j<=tot;j++){int now=prime[j];if(now>n/i||now>v[i]) break;v[now*i]=now;}}return; }int main() {scanf("%lld",&n);findprime();for(int i=1;i<=tot;i++){for(ll j=prime[i];j<=n;j*=prime[i]){c[i]+=n/j;c[i]%=mod;}}ll ans=1;for(int i=1;i<=tot;i++){ans=(ans*(2*c[i]+1))%mod;}printf("%lld\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的不定方程（质数与因数）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。