锐客网

  1. 首页 > it技术 > >

[CF819D]Mister B and Astronomers

gcd与exgcd

有n个wzd在仰望星空，第一个wzd会在第0秒仰望星空，第i个wzd会在i-1个仰望完之后的a[i]秒后仰望星空一秒。第n个仰望完后第一个接着，一直循环下去。
有一颗星星在一闪一闪，他有一个参数T，含义是每T秒闪一次，但不知道它从0~T-1秒的哪一个时候会闪。
定义一个wzd的“幸运值”为满足以下条件的x的个数： x∈[0,T?1]x ∈ [ 0 , T ? 1 ] ，星星从第x秒开始闪时，这个wzd是第一个看到的人。
问每个wzd的幸运值
T<=1e9,n<=2e5
解题思路
【[CF819D]Mister B and Astronomers】定义 y[i]=∑i=2..ia[i],S=∑i=1..na[i]y [ i ] = ∑ i = 2.. i a [ i ] , S = ∑ i = 1.. n a [ i ] 那么第i个wzd仰望星空的时间就是 x?S+y[i]x ? S + y [ i ] 。
对于一个闪烁开始时刻t，如果有两个wzd都看到了这颗星星，一定是x小的，或者x相同时y小的那个wzd最先看到。
那么我们换个角度考虑这个问题。首先，对于 i 我们知道对于S和T，跳来跳去在模意义下会形成gcd(S,T)个环，所以我们把i按y[i]%gcd(S,T)分组，假设模出来的数是z，那么他分到第z组。
对于一个组z，我们从 [0,T?1]的z[ 0 , T ? 1 ] 的 z 开始跳，确定每个元素i在第几次跳的时候被碰到，记为X[i]，然后升序排序，每个wzd的幸运值就是X[i+1]-X[i]了。
实现可以用set+map乱搞。
代码

#include #include #include #include #include #include //开 O2！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！ using namespace std; #define fo(i,j,k) for(i=j; i<=k; i++) #define fd(i,j,k) for(i=j; i>=k; i--) #define cmax(a,b) (a=(a>b)?a:b) #define cmin(a,b) (a=(a mp,czy; multiset tr[N]; multiset :: iterator it; int pp[N],a[N],n,T,A,B,S,d,rem,ka,ts,prt[N],x[N],y[N],i; int exgcd(int a,int b,int &x,int &y) { if (!b) { x=1; y=0; return a; } int ret=exgcd(b,a%b,y,x); y-=a/b*x; return ret; } int main() { freopen("d.in","r",stdin); //freopen("d.out","w",stdout); scanf("%d %d",&T,&n); fo(i,1,n) { scanf("%d",a+i); if (i!=1) y[i]=(y[i-1]+a[i])%T; if (!mp[y[i]]) mp[y[i]]=i,pp[i]=1; S=(S+a[i])%T; } d=exgcd(S,T,A,B); S/=d; T/=d; A%=T; if (A<0) A+=T; fo(i,1,n) if (pp[i]) { ka=y[i]%d; if (!czy[ka]) czy[ka]=++ts; rem=y[i]-ka; ka=czy[ka]; // aS+bT=rem rem/=d; x[i]=1ll*A*rem%T; tr[ka].insert(x[i]); } fo(i,1,n) if (pp[i]) { ka=czy[y[i]%d]; it=tr[ka].find(x[i]); it++; prt[i]=-x[i]; if (it==tr[ka].end()) { prt[i]+=T; it=tr[ka].begin(); } prt[i]+=*it; } fo(i,1,n) printf("%d ",prt[i]); }

    推荐阅读


      上一篇：13朝古都

      下一篇：#|OkHttp ConnectInterceptor 连接的建立