当前位置: 首页 > news >正文

用什么软件做网站seo好今日关注

用什么软件做网站seo好,今日关注,做网站超链接用什么软件,网站开发教程视频原题链接:码题集OJ-跑步 题目大意:一个n个人在绕圈跑,第i个人跑一圈的时间是i分钟,每二个人位置相同就会打一次招呼,如果同时来到终点,他们就会停下来,请问会打多少次招呼? 思路&a…

原题链接:码题集OJ-跑步

题目大意:一个n个人在绕圈跑,第i个人跑一圈的时间是i分钟,每二个人位置相同就会打一次招呼,如果同时来到终点,他们就会停下来,请问会打多少次招呼?

思路:首先可以想到这n个人会跑他们的最小公倍数的圈数之后停下来。最小公倍数用ores代替,如何求最小公倍数呢?一个数肯定是由一堆质数相乘得到的,所以只要求出1-n中每个质数的最高次幂就可以了,例如说要求1 2 3 4 5 6 7 8 9 10的最小公倍数,那么其实就是求1 1 1 1 5 1 7 8 9 1的最小公倍数,因为8=2*2*2,那么2的这个质数本身就不重要了。p字母为质数,那么这个质数的最高次幂就是\log n /\log p

因为跑的快的不会被跑的慢的人追到,那么可以想到一个必定超时的方案,那就是用二层for来枚举。对于第i个人,他前面的所有人都会被他追到,所有第i个人的贡献就是ores*n/i-ores*n/(i+1)+ores*n/i-ores*n/(i+2)......双重循环枚举就可以了,但是数据范围明显会超时,可以想到在双重枚举的过程中肯定会有很多不必要的计算,一个人可以追前面的人,也可以被后面的人追上,如果是追前面的人,那么n/i是减数,一共有(n-i)个人可以被追上,如果是被追上那么n/i就是被减数,一共有(i-1)个人,那么减数减去被减数的数量乘上当前数跑的圈数就是打招呼的数量也就是(n-2*i+1)*(n/i)。例如说1 2 3,如果双重循环计算,第一个人的贡献是:6-1/2*6+6-1/3*6,第二个人的贡献是:1/2*6-1/3*6,如果单独计算,那么第一个的贡献就是:6*(3-2*1+1),第二个人的贡献就是:6/2*(3-2*2+1)

那这样题目就很明显了,但是因为数据会很大要取模,所以需要算出从1-n的所有数的逆元。对于1-n的逆元可以线性的求出。

inv数组表示逆元

p=q*i+r 

二边同时mod p

0=q*i+r

二边同时乘上i的逆元和r的逆元

0=q*r^{-1}+i^{-1}

移项变形

i^{-1}=-q*r^{-1}=-p/i*pmodi^{-1} 

q=p/i,r^-1=(p%i)^-1,因为是mod意义下的计算,所以右边可以加上p*(p%i)^-1.

最终就是inv[i]=(mod-mod/i)*inv[mod%i]%mod.

//冷静,冷静,冷静
//调不出来就重构
#pragma GCC optimize(2)
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e7+10,mod=998244353;
ll inv[N],prime[N],n;
bool vis[N]; 
ll ksm(ll a,ll b)
{ll ans=1;do{if(b&1)ans*=a;a*=a;b>>=1;a%=mod;ans%=mod;}while(b); return ans;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);inv[1]=1;cin>>n;ll cnt=0,ores=1;for(int i=2;i<=n;i++){inv[i]=(mod-mod/i)*inv[mod%i]%mod;//求每个数的逆元 if(!vis[i])prime[cnt++]=i,ores=ores*ksm(i,log(n)/log(i))%mod;//求n范围内的质数的最高次幂的乘积 for(int j=0;j<cnt&&i*prime[j]<=n;j++){vis[i*prime[j]]=1;if(i%prime[j]==0)break;}}ll ans=0;for(int i=1;i<=n;i++){ll op=ores*inv[i]%mod;//这个人跑的圈数 ans=(ans+op*(n-2*i+1)%mod+mod)%mod; }cout<<ans;return 0;
}

http://www.dt0577.cn/news/50336.html

相关文章:

  • dreamweaver网站模板下载杭州seo顾问
  • 门户网站建设情况报告百度一下的网址
  • 阿里云网站建设部署与发布百度竞价官网
  • dw怎么做网站布局网络推广网站推广
  • 企业解决方案模板广州新塘网站seo优化
  • 怎么做网盘搜索网站游戏推广赚佣金的平台
  • 代理网站地址公众号seo排名软件
  • 做网站的企业有哪些谷歌独立站
  • 网页设计html代码成品图片百度seo软件是做什么的
  • 响应式网站一般做多大推广团队
  • 做网站需要什么费用优化水平
  • 微信网站图片链接怎么做seo排名软件价格
  • seo网站排名的软件今天国际新闻最新消息10条
  • 免费php网站模板济南百度代理
  • 外链网盘网站手机网站制作
  • 柳州市安全教育平台成都seo论坛
  • wordpress二次开发视频短视频seo
  • 网站响应式首页模板营销技巧培训
  • 建新建设集团有限公司网站黄山seo排名优化技术
  • 腾讯网页游戏排行榜南宁白帽seo技术
  • 公司网站优化要怎么做做网页设计一个月能挣多少
  • 做网站的名字大全谷歌seo优化排名
  • 企业网站建设可以分为哪些层次深圳网站营销seo费用
  • 免费360地图手机版北京网站seo服务
  • 做招投标应该了解的网站广州宣布5条优化措施
  • 装修网站建设方案无锡seo优化
  • wordpress搜插件错误谷歌推广和seo
  • 如何做自己的项目网站aso优化工具
  • 网站策划书免费互联网营销师考证多少钱
  • 高端网站开发报价最佳磁力搜索天堂