2024百度之星 跑步

原题链接：码题集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字母为质数，那么这个质数的最高次幂就是。

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

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

inv数组表示逆元

 

二边同时mod p

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

移项变形

 

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;
}