[Acwing] 220. 最大公约数是否为素数的数对 暂记作板子

前言

传送门 : 显然如果记作板子的话,是不能有多大的思维提升的

思路

题目要求 1 − N 1-N 1−N中找到 g c d ( x , y ) = p gcd(x,y)=p gcd(x,y)=p等价于 g c d ( x / p , y / p ) = 1 gcd(x/p,y/p)=1 gcd(x/p,y/p)=1

即问题转换为,求 x , y x,y x,y的互质,因此问题转换为模板 201.可见的数对

Mycode

// Problem: 最大公约数
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/222/
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i=b;i--)

typedef priority_queue  Pri_m;
typedef pair pii;
typedef vector VI;
map mp;

const int N  = 1e7+10;


int primes[N], cnt;
bool st[N];
int phi[N];
ll s[N];

void init(int n)
{
    for(int i=2;i