锐客网

  1. 首页 > it技术 > >

[数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends

数论

两道类似的题
819D 考虑一个人应该能够观察的位置ti,(ti+S)modT,(ti+2S)modT?
这个应该是形成gcd(S,T)个环，每个环是长度Tg
然后把同一个环的一起处理，把点放到环上，那么沿环的方向到下一个点为止应该都是归到这个点答案里面的

#include #include #include #include using namespace std; typedef long long ll; typedef pair abcd; #define read(x) scanf("%I64d",&(x))inline abcd EXGCD(ll a,ll b){ if (!b) return abcd(1,0); abcd t=EXGCD(b,a%b); return abcd(t.second,t.first-a/b*t.second); } inline ll Calc(ll a,ll b,ll p){ abcd t=EXGCD(a,p); ll d=t.first*a+t.second*p; return ((t.first%p+p)*(b/d))%p; }const int N=200005; ll n,S,T,g,C; ll a[N],_a[N]; int idx[N]; abcd t[N]; int tot; ll ans[N]; set Set; inline bool cmp(int x,int y){ return a[x]%g==a[y]%g?a[x]y]:a[x]%gy]%g; }int main(){ freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(T); read(n); for (int i=1; i<=n; i++) read(_a[i]),S+=_a[i]; for (int i=1; i

516E 【[数论] Codeforces 819D R #421 D.Mister B and Astronomers & 516E R #292 E. Drazil and His Happy Friends】考虑如果一边某个人在时刻t被标记，那么至少n时刻后(t+n)modm号人也必然被标记，也就是一个环上求最早被访问到的距离，还是放到环上，到下一个点位置应该都是以这个点作为最优的
最后两边被访问到最晚的时间就是答案
#include #include #include #include using namespace std; typedef long long ll; typedef pair abcd; #define read(x) scanf("%d",&(x))inline abcd EXGCD(ll a,ll b){ if (!b) return abcd(1,0); abcd t=EXGCD(b,a%b); return abcd(t.second,t.first-a/b*t.second); } inline ll Calc(ll a,ll b,ll p){ abcd t=EXGCD(a,p); ll d=t.first*a+t.second*p; return ((t.first%p+p)*(b/d))%p; }const int N=200005; int S,T,g; int a[N],b[N]; ll ans; abcd t[N]; int _t; set Set; inline bool cmp(abcd x,abcd y){ return x.first%g==y.first%g?(x.first==y.first?x.second

    推荐阅读


    上一篇：线段树|[类欧几里得算法 线段树] BZOJ 1938 [CROATIAN2010] ALADIN

    下一篇：类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake