锐客网

  1. 首页 > it技术 > >

数论|Mister B and Astronomers CodeForces - 819D（数论）

数论codeforce

Mister B and Astronomers CodeForces - 819D（数论） 题目大意 有n个观察员，第一个观察员在0秒开始观察星空，随后第i个观察员会在第i-1个观察员之之后 a i a_i ai?秒进行观察，第一个观察员也会在第n个观察员观察后 a 1 a_1 a1?秒观察，有一颗星星其闪烁的周期为T，其第一次闪烁的时间不确定.问每个观察员有多少种可能成为第一个观察到这颗星星的人
解题思路 假设第i个观察员第一次观察的时刻为 b i b_i bi?，观察员的观察周期为S，则本题实际上就是求解
( b i + k ? s ) % T = y ( y ∈ ( 0 , T ? 1 ) ) (b_i+k*s)\%T=y(y\in (0,T-1)) (bi?+k?s)%T=y(y∈(0,T?1))
对于每个y，使得k最小的 b i b_i bi?
【数论|Mister B and Astronomers CodeForces - 819D（数论）】对此我们可以对原等式进行转化
b i % T + ( k ? s ) % T = y b_i\%T+(k*s)\%T=y bi?%T+(k?s)%T=y
其中 ( k ? s ) % T = q ? g c d ( s , T ) ( q ∈ Z + ) (k*s)\%T=q*gcd(s,T)(q\in Z^+) (k?s)%T=q?gcd(s,T)(q∈Z+)先令 d = g c d ( s , T ) d=gcd(s,T) d=gcd(s,T)因此凡是使得 b i % T % d = y % d b_i\%T\%d=y\%d bi?%T%d=y%d的y均可被 b i b_i bi?观察到，但还需要求为第一次观察到的.
继续分析.由上述的分析结果我们可以将所有的 b i % T b_i\%T bi?%T分成d类由此每一类都只会在自己这一类中跳动，每类都有 T d \frac{T}{d} dT?个元素
而所有的y也将分布在这些类中，因此所有的y也将分布在每类的任两个数之间
因此只需求出所有的类中的数与其下一个数之间的距离即可
其中为了方便求距离我们需要对每个数引入一个坐标，其中每个数的位置可以表示为 ( b i + k ? s ) % T % d = y % d ( y ∈ ( 0 , T ? 1 ) ) (b_i+k*s)\%T\%d=y\%d(y\in (0,T-1)) (bi?+k?s)%T%d=y%d(y∈(0,T?1))方程的解k
AC代码

#include using namespace std; const int sz=2e5+5; typedef long long LL; unordered_map mp,id; unordered_map hs; set s[sz]; int vis[sz]; int arr[sz]; int nos[sz]; int ans[sz]; LL exgcd(LL a,LL b,LL &x,LL &y) { if(b==0) { x=1,y=0; return a; } LL ret=exgcd(b,a%b,y,x); y-=a/b*x; return ret; } LL getInv(LL a,LL mod) { LL x,y; exgcd(a,mod,x,y); return x; } int32_t main() { int T,n; cin>>T>>n; int S=0; memset(vis,0,sizeof(vis)); for(int i=1; i<=n; i++) cin>>arr[i],S=(S+arr[i])%T; arr[1]=0; for(int i=2; i<=n; i++) arr[i]=(arr[i]+arr[i-1])%T; for(int i=1; i<=n; i++) if(!hs.count(arr[i])) hs[arr[i]]=1,vis[i]=1; int d=__gcd(S,T); T/=d; S/=d; int inv=getInv(S,T); int no=0; for(int i=1; i<=n; i++) { int t=arr[i]%d; if(!id[t]) id[t]=++no; nos[i]=1LL*inv*(arr[i]-t)/d%T; s[id[t]].insert(nos[i]); } for(int i=1; i<=n; i++) { if(!vis[i]) {ans[i]=0; continue; } int ids=id[arr[i]%d]; set::iterator p=s[ids].find(nos[i]); p++; if(p==s[ids].end()) ans[i]=(*s[ids].begin())+T-nos[i]; else ans[i]=(*p)-nos[i]; } for(int i=1; i<=n; i++) cout<

    推荐阅读


    上一篇：okhttp请求完整流程图

    下一篇：Android|Android Studio 解决导入其他项目慢或者卡死的问题