正解:数论

解题报告:

传送门!

首先考虑怎么样的数可能出现在$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=,N=+;
int l,r,sum,fac[N],ifac[N];
bool vis[N]; il int read()
{
rc ch=gc;ri x=;rb y=;
while(ch!='-' && (ch>'' || ch<''))ch=gc;
if(ch=='-')ch=gc,y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
return y?x:-x;
}
il int power(ri x,ri y){int ret=;while(y){if(y&)ret=1ll*ret*x%mod;x=1ll*x*x%mod;y>>=;}return ret;}
il void pre(ri n)
{
fac[]=;rp(i,,n)fac[i]=1ll*fac[i-]*i%mod;
ifac[n]=power(fac[n],mod-);my(i,n-,)ifac[i]=1ll*ifac[i+]*(i+)%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]=;}
ri as=,n=r-l+;
rp(i,sum,n)as=(as+1ll*i*sum%mod*C(n-sum,n-i)%mod*fac[n-i]%mod*fac[i-]%mod)%mod;
printf("%d\n",as);
return ;
}

最后放下代码鸭!

最新文章

  1. IOS-细节错误
  2. 数据结构和算法 c#&ndash; 1.单项链表
  3. 无法远程连接ubuntu下的mysql
  4. Java基础-数据类型int,short,char,long,float,double,boolean,byte
  5. H264码流打包分析(精华)
  6. javascript editor
  7. ios 用LLDB查看模拟器文件路径以及一些常用的命令
  8. HDOJ(HDU) 2091 空心三角形
  9. gcc基本用法
  10. STL中的set容器的一点总结(转)
  11. JDBC (一)
  12. Linux下*.tar.gz/.tar.bz2 文件解压缩安装命令
  13. SpringBoot技术栈搭建个人博客【后台开发】
  14. 使用Xshell调用linux的图形界面!
  15. 一个数组中两个数的和为N,找出这两个数字的下标
  16. saxon 处理xslt
  17. html学习_认识html
  18. Spring Boot(六):如何使用mybatis
  19. Linux 搭建 Jenkins
  20. orika core工具对实体(Bean)进行深度拷贝

热门文章

  1. 卷积、矩阵乘积、高斯模糊滤波(降噪)、空域计算(2D卷积计算)、频域计算(FFT)的理解
  2. cvCreateImage
  3. Java知多少(101)图像缓冲技术
  4. Cocos2dx网络读取图片
  5. 概率霍夫变换(Progressive Probabilistic Hough Transform)原理详解
  6. vmware-hostd.exe 占用443端口导致Apache无法正常启动?
  7. Failed to read schema document &#39;http://code.alibabatech.com/schema/dubbo/dubbo.xsd&#39;问题解决方法
  8. Service 中的 onStart 和 onStartCommand
  9. [Python] 06 - Modules --&gt; Packages
  10. 富可视M310刷机包 MIUIV5 红米开发版 闪光 美化 稳定