洛谷P4562 [JXOI2018]游戏 数论
正解:数论
解题报告:
首先考虑怎么样的数可能出现在$t(i)$那个位置上?显然是$[l,r]$中所有无法被表示出来的数(就约数不在$[l,r]$内的数嘛$QwQ$
所以可以先把这些数筛出来
具体怎么筛的话,最原始的方法就埃氏筛?
然后显然可以线性筛,但我$jio$得大概快不到哪儿去而且麻烦一些懒得打了所以直接用的埃氏筛
然后现在就筛出来,有$sum$个满足条件的数了,考虑怎么算贡献?(先注明下,,,可能有些±1的细节下面都直接略过了$QAQ$
就先枚最后一个这样的数出现的位置$x$(也就是$t(i)$的取值
首先它自己会有$x$的贡献
然后在它后面可以从$n-sum$个数中选出$n-x$个数,而且这些数可以随便排列,所以有$C(n-x,n-sum)\cdot (n-x)!$
然后在它之前的数可以随便排列,所以有$(x-1)!$
最后这个数是从$sum$个数中选出来的所以还有$C(sum,1)$
综上,可以列出式子,$ans=\sum i\cdot sum\cdot (i-1)!\cdot (n-x)!\cdot C(n-x,n-sum)$
然后这题好像还有优化,,,但是我懒得落实了(bushi
反正一时半会儿应该不会再写优化了,,,如果很久很久之后考古出了这篇博客也许会填下QAQ?(四舍五入就是咕了:D
#include<bits/stdc++.h> using namespace std; #define il inline #define ll long long #define gc getchar() #define ri register int #define rc register char #define rb register bool #define rp(i,x,y) for(ri i=x;i<=y;++i) #define my(i,x,y) for(ri i=x;i>=y;--i) const int mod=1000000007,N=10000000+10; int l,r,sum,fac[N],ifac[N]; bool vis[N]; il int read() { rc ch=gc;ri x=0;rb y=1; while(ch!='-' && (ch>'9' || ch<'0'))ch=gc; if(ch=='-')ch=gc,y=0; while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc; return y?x:-x; } il int power(ri x,ri y){int ret=1;while(y){if(y&1)ret=1ll*ret*x%mod;x=1ll*x*x%mod;y>>=1;}return ret;} il void pre(ri n) { fac[0]=1;rp(i,1,n)fac[i]=1ll*fac[i-1]*i%mod; ifac[n]=power(fac[n],mod-2);my(i,n-1,0)ifac[i]=1ll*ifac[i+1]*(i+1)%mod; } inline int C(ri n,ri m){return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;} int main() { // freopen("4562.in","r",stdin);//freopen("4562.out","w",stdout); l=read();r=read();pre(r); rp(i,l,r)if(!vis[i]){++sum;for(ri j=i;j<=r;j+=i)vis[j]=1;} ri as=0,n=r-l+1; rp(i,sum,n)as=(as+1ll*i*sum%mod*C(n-sum,n-i)%mod*fac[n-i]%mod*fac[i-1]%mod)%mod; printf("%d\n",as); return 0; }