做气体检测仪的网站,贵州高端网站开发,网站建设三合一 500元,辽宁城乡建设集团成立网站原题链接#xff1a;码题集OJ-跑步
题目大意#xff1a;一个n个人在绕圈跑#xff0c;第i个人跑一圈的时间是i分钟#xff0c;每二个人位置相同就会打一次招呼#xff0c;如果同时来到终点#xff0c;他们就会停下来#xff0c;请问会打多少次招呼#xff1f;
思路码题集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的最小公倍数因为82*2*2那么2的这个质数本身就不重要了。p字母为质数那么这个质数的最高次幂就是。
因为跑的快的不会被跑的慢的人追到那么可以想到一个必定超时的方案那就是用二层for来枚举。对于第i个人他前面的所有人都会被他追到所有第i个人的贡献就是双重循环枚举就可以了但是数据范围明显会超时可以想到在双重枚举的过程中肯定会有很多不必要的计算一个人可以追前面的人也可以被后面的人追上如果是追前面的人那么是减数一共有(n-i)个人可以被追上如果是被追上那么就是被减数一共有(i-1)个人那么减数减去被减数的数量乘上当前数跑的圈数就是打招呼的数量也就是。例如说1 2 3如果双重循环计算,第一个人的贡献是,第二个人的贡献是如果单独计算那么第一个的贡献就是,第二个人的贡献就是。
那这样题目就很明显了但是因为数据会很大要取模所以需要算出从1-n的所有数的逆元。对于1-n的逆元可以线性的求出。
inv数组表示逆元 二边同时mod p 二边同时乘上i的逆元和r的逆元 移项变形 qp/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)
#includebits/stdc.h
#define endl \n
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pairll,ll pii;
const int N1e710,mod998244353;
ll inv[N],prime[N],n;
bool vis[N];
ll ksm(ll a,ll b)
{ll ans1;do{if(b1)ans*a;a*a;b1;a%mod;ans%mod;}while(b); return ans;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);inv[1]1;cinn;ll cnt0,ores1;for(int i2;in;i){inv[i](mod-mod/i)*inv[mod%i]%mod;//求每个数的逆元 if(!vis[i])prime[cnt]i,oresores*ksm(i,log(n)/log(i))%mod;//求n范围内的质数的最高次幂的乘积 for(int j0;jcnti*prime[j]n;j){vis[i*prime[j]]1;if(i%prime[j]0)break;}}ll ans0;for(int i1;in;i){ll opores*inv[i]%mod;//这个人跑的圈数 ans(ansop*(n-2*i1)%modmod)%mod; }coutans;return 0;
}
