【CF819D】Mister B and Astronomers
题意：小鼠Jack想当太空人（哦不，太空鼠）！为此，它在夜晚带领一堆小朋友一起来到户外看星星。一共有 $n$ 只小鼠，这些小鼠围成一圈轮流观察夜空。具体地，第 $i$ 只小鼠会在第 $(i-1)\%n$ 只小鼠观察夜空之后的第 $a_i$ 秒，抬头观察 $1$ 秒钟的夜空。即： $1$ 号小鼠在第 $0$ 秒观察夜空，$2$ 号小鼠在第 $a_2$ 秒观察夜空，$3$ 号小鼠在第 $a_2+a_3$ 秒观察夜空 ... $1$ 号小鼠在第 $a_2+a_3+...+a_n+a_1$ 秒观察夜空。今晚小鼠们特别想观察到的是名为 $X$ 的星星，但是他们并不知道 $X$ 会在什么时候闪烁，只知道 $X$ 会每隔 $T$ 秒闪烁一次，每次闪烁一秒钟，且第一次闪烁的时间在 $0$ 到 $T-1$ 之间。如果一个小鼠在观察夜空时，$X$ 恰好在闪烁，则这个小鼠就会在这一秒发现 $X$ 闪烁。我们定义第 $i$ 只小鼠的幸运值为：有多少 $tin [0,T),tin Z$ ，满足 如果 $X$ 第一次闪烁的时间是第 $t$ 秒，那么 $i$ 将会是第一个发现 $X$ 闪烁的小鼠。现在Jack想知道每个小鼠的幸运值是多少。
题解：设$S=sum a_i$，那么假如第i只小鼠在第k*S+x秒钟观察到了星星，而这个时刻的星星已经被观察过了，就是说明存在一只小鼠在第k'*S+y秒钟观察到了星星，其中k'<k或k'=k且y<x，对于后一种情况我们特判掉。对于前一种情况，我们得到同余式(k-k')S=y-x(mod T)，我们想知道的是k-k'的最小值。
现在我们只需要解这个同余式即可，先将S和T都除以gcd(S,T)，同时将所有x按%gcd分组，显然只有同一组内的才会产生贡献。然后我们用exgcd解出k*S=-x(mod T)的k，在set里找一下k的前驱就能得到最小的k-k'了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=200010;
typedef long long ll;
int n,m;
ll S,T,d;
int ban[maxn],p[maxn];
ll t[maxn],k[maxn],top[maxn],ans[maxn];
vector<int> v[maxn];
vector<int>::iterator vi;
set<ll> s;
set<ll>::iterator si;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b)
{
x=1,y=0;
return a;
}
ll ret=exgcd(b,a%b,x,y),t=x;
x=y,y=t-a/b*x;
return ret;
}
ll gcd(ll a,ll b)
{
return !b?a:gcd(b,a%b);
}
inline bool cmp(const int &a,const int &b)
{
return (t[a]%d==t[b]%d)?(a<b):(t[a]%d<t[b]%d);
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();
return ret*f;
}
int main()
{
T=rd(),n=rd();
int i;
S=rd();
for(i=2;i<=n;i++) t[i]=rd(),S+=t[i],t[i]+=t[i-1];
ll x,y,b;
d=exgcd(S,T,x,y);
b=T/d,x=(x%b+b)%b;
for(i=1;i<=n;i++)
{
if(s.find(t[i]%T)!=s.end()) ban[i]=1;
else s.insert(t[i]%T),p[++p[0]]=i;
}
if(S%T==0)
{
for(i=1;i<=n;i++) printf("%d ",1-ban[i]);
return 0;
}
sort(p+1,p+p[0]+1,cmp);
for(i=1;i<=p[0];i++)
{
if(i==1||t[p[i]]%d!=t[p[i-1]]%d) m++;
v[m].push_back(p[i]);
}
for(i=1;i<=m;i++)
{
s.clear();
for(vi=v[i].begin();vi!=v[i].end();vi++)
{
k[*vi]=x*(t[*vi]/d%b)%b;
if(s.find(k[*vi])!=s.end()) ban[*vi]=1;
else s.insert(k[*vi]);
}
for(vi=v[i].begin();vi!=v[i].end();vi++)
{
si=s.upper_bound(k[*vi]);
if(si==s.end()) si=s.begin(),ans[*vi]=(*si)+b-k[*vi];
else ans[*vi]=(*si)-k[*vi];
}
}
for(i=1;i<=n;i++) printf("%lld ",ans[i]);
return 0;
}