Codeforces Round #505 (rated, Div. 1 + Div. 2) B. Weakened Common Divisor

题意：定义弱因数x为满足对于一对数{a,b}，{ x | !(x%a) || !(x%b) }

现在问你n对数的公共弱因数

这场比赛没打，但是吧赛时看了下题，和室友口胡了下正解是sqrt(a)+sqrt(b)时间计算出某对数的所有因数，设去重后一共有x个，之后for一遍所有对，总复杂度是

然后早上一写，submit，TLE on test99

woc？？？t最后一组？？？？

稍微再想一下我们可以发现，由于1e9内某些数的因子数量或超过1e3,例如{1889727840,1715313600},总个数x去重后大概有2e3多点

这样的话时间就是3e8多点，很容易被卡

那么怎么解决呢-----只遍历素因子就好了，素因子只有logn个，那么总复杂度就是了

对于所有因子，他们等效于他们的素因子，所以可以直接用素因子去遍历.

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include
using namespace std;
typedef long long ll;
inline int readn()
{int x=0;char ch=getchar();while(ch>'9'||ch<'0') ch=getchar();while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();return x;
}
vector > vp;
set st;
int main()
{int n=readn();vp.clear(),st.clear();for(int i=0;i

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
int a[maxn];
int b[maxn];
vector v;
int main()
{int n;scanf("%d",&n);for(int i=0;i