Submission #73484466

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
typedef pair<ll,ll> PII;
typedef array<ll,2> a2;
typedef array<ll,3> a3;
int n,m,k;
int a,b;
bool tf[N];

vector<int> e[N];
int getid(int x,int y){
    return x*n+y;
}

void 打卡啦摩托(){
    cin>>n>>a>>b;
    for(int i=0;i<n*n;i++){
        int x=i/n,y=i%n;
        int z=b*x+y*a;
        z%=n;
        // cout<<x<<" "<<y<<" "<<y<<" "<<z<<endl;
        e[getid(y,z)].push_back(i);
    }
    queue<int> q;
    for(int i=0;i<n;i++){
        q.push(getid(0,i));
        tf[getid(0,i)]=1;
        q.push(getid(i,0));
        tf[getid(i,0)]=1;
        
    }
    while(q.size()){
        int t=q.front();
        q.pop();
        for(auto j:e[t]){
            if(!tf[j]){
                // cout<<t<<" "<<j<<endl;
                q.push(j);
                tf[j]=1;
            }
        }
    }
    int ans=0;
    for(int i=0;i<n*n;i++){
           
        if(!tf[i]){
            // cout<<i/n<<" "<<i%n<<endl;
            ans++;
        }
    }
    cout<<ans<<endl;
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _=1;
    // cin>>_;
    while(_--){
        打卡啦摩托();
    }
}

Submission Info

Judge Result