不规则轮回

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

给定 n 个数对，对于每个数对 (x,y) 会持续执行以下操作直到 x=y：
- 当 x > y 时，x = x - y
- 当 x < y 时，y = y - x
同时有 q 次询问，每次给定一个数对 xq,yqx_q,y_qxq,yq, 问上述给定的 n 个数对的执行过程中出现了 xq,yqx_q,y_qxq,yq 的次数。

输入描述:

第一行一个正整数n，代表数对个数。

接下来n行，每行两个正整数(x,y)。

接下来一行输入一个正整数q，代表询问次数。

接下来q行，每行两个正整数(xq,yq)(x_q,y_q)(xq,yq)。

1≤n≤1×1031 \leq n \leq 1 \times 10^{3}1≤n≤1×103
1≤q≤1×1031 \leq q \leq 1 \times 10^{3}1≤q≤1×103
1≤x,y,xq,yq≤1×1041 \leq x,y,x_q,y_q \leq 1 \times 10^{4}1≤x,y,xq,yq≤1×104

输出描述:

输出n行，表示每次询问的答案。

示例1

输入

复制6 5 10 8 9 5 7 8 9 1 5 2 6 3 7 1 5 5 3 6

输出

复制

2
1
0

#include<iostream>
using namespace std;
struct sd{
    int a,b;
}con[1010];
long long  s[10010][10010]={};
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>con[i].a>>con[i].b;
        s[con[i].a][con[i].b]++;
        while(con[i].a!=con[i].b){
            if(con[i].a>con[i].b) con[i].a-=con[i].b; 
            else con[i].b-=con[i].a;
            s[con[i].a][con[i].b]++;
        }
    }
    int q,x,y;
    cin>>q;
    while(q--){
        cin>>x>>y;
        cout<<s[x][y]<<endl;
    }
    return 0;
}

输入描述:

输出描述:

输入

输出

相关文章