Submission #32185372

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read
int gcd(int a,int b){
  while(b!=0){
    a=a%b;
    swap(a,b);
  }
  return a;
}

int fa[200010];
int a[4];
int inner[200010]; // 组内部最小间隔, 一定是n的因子
int tofa[200010]; // 跨组偏移距离
ll n;

int getfa(int i){
  if(i == fa[i]) return i;
  int newfa = getfa(fa[i]);
  tofa[i] = ((tofa[i] + tofa[fa[i]])%n)%inner[newfa];
  return fa[i] = newfa;
}

// new root u
// u and v is old root
void link(int u,int v,int off){
  fa[v] = u;
  inner[u] = gcd(inner[u],inner[v]);
  tofa[v] = off % inner[u];
}

int main(){
  n = read();
  ll q = read();
  ll ans = n*n;
  iota(fa,fa+n,0);
  fill(inner,inner+n,n);
  rep(i,0,q){
    rep(j,0,4) a[j] = read();
    per(j,0,4) (a[j] += n-a[0])%=n;
    int g1 = a[1] - a[0];
    int g2 = (a[3]-a[2]+n)%n;
    int off = a[2] - a[0];
    int f1 = getfa(g1);
    int f2 = getfa(g2);
    // 同组更新内部间隔
    if(f1 == f2){
      // ans -= inner[f1] - inner[f1];
      // printf("SAME %d[%d] => ",f1,inner[f1]);
      ans -= inner[f1];
      inner[f1] = gcd(inner[f1], 2*n + tofa[g1] - tofa[g2] + off); // 不是off
      ans -= -inner[f1];
      // printf("%d \n",inner[f1]);
    }else{ // 不同组 合并组
      // printf("DIFF %d[%d] + %d[%d] => ",f1,inner[f1],f2,inner[f2]);
      // g1->f1, g2->f2
      // f2->f1?
      // f1 - f2 = (f1 - g1) - (f2 - g2) + (g2 - g1)
      // ans -= inner[f1] + inner[f2] - inner[f1];
      ans -= inner[f1] + inner[f2];
      link(f1,f2, (2*n + tofa[g1] - tofa[g2] + off)%n);
      ans -=  - inner[f1];
      // printf("%d \n",inner[f1]);
    }
    printf("%lld\n",ans);
  }

  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:10:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   10 | ll read(){ll r;scanf("%lld",&r);return r;} // read
      |                ~~~~~^~~~~~~~~~~

Judge Result