SPOJ_COMDIV_TLE
kaziamir
c_cpp
a year ago
775 B
8
Indexable
#include<bits/stdc++.h> using namespace std; #define gcd(a,b) __gcd(a,b) #define siz 1000009; vector<set<int>> divs; void store_divisors(){ int N = siz; for(int i = 1; i<=N; i++){ set<int> tmp; for(int j = 1; j*j<=i;j++){ if(i%j==0){ tmp.insert(j); if(i/j!=j){ tmp.insert(i/j); } } } divs.push_back(tmp); } } void solution(){ int tcase; scanf("%d", &tcase); for(int tc = 1; tc<=tcase; tc++){ int A,B; scanf("%d %d", &A,&B); printf("%d\n",divs[gcd(A,B)-1].size()); } } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); store_divisors(); solution(); }
Editor is loading...
Leave a Comment