当前位置：网站首页>AtCoder Beginner Contest 254

AtCoder Beginner Contest 254

2022-07-02 15:03:00 【Not Zhang Pangpang】

List of articles

D - Together Square
F - Rectangle GCD

D - Together Square

The question ：
Calculate the number of pairs less than or equal to $\leq n \leq 2×10^5)$ Of $i, j$ , Satisfy $i \times j$ It's a square number
Ideas ：
If $i$ It's a square number , that $j$ It's also a square number .
otherwise , $j$ It should be square times $i$ A prime factor with an odd number of occurrences in

#include<bits/stdc++.h>
#define pb push_back
typedef long long ll;
using namespace std;
typedef pair<int,int> PII;
const int maxn=2e5+7;
int n,vis[maxn];
int main()
{
    
	scanf("%d",&n);
	vector<int>v;
	for(int i=1;;i++)
	{
    
		if(i*i>n) break;
		vis[i*i]=1;v.pb(i*i);
	}
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
    
		if(vis[i]) ans+=v.size();
		else
		{
    
			int nn=i;
			for(int j=1;j<v.size();j++)
			{
    
				while(nn%v[j]==0)
				{
    
					nn/=v[j];
				}
			}
			for(int j=0;j<v.size();j++)
			{
    
				if(v[j]*nn>n) break;
				ans++;
			}
		}
	}
	printf("%lld\n",ans);
}

F - Rectangle GCD

The question ：
There is a length of $n(1≤n≤2×10^5)$ Array of $A,B(1≤A _i,B_i≤10^9)$ , And one. $n \times n$ The square of , The first $i$ Xing di $j$ The number of columns is $A_i+B_j$
Yes $q(1≤q≤2×10^5)$ Time to ask , Ask all the numbers in a rectangular area at a time $\gcd$
Ideas ：
The number in the rectangle is
$a_i+b_j \quad a_{i}+b_{j+1} \quad a_{i}+b_{j+2} \quad a_{i}+b_{j+3} \quad ...\\ a_{i+1}+b_{j} \quad a_{i+1}+b_{j+1} \quad a_{i+1}+b_{j+3} \quad a_{i+1}+b_{j+2} \quad ...\\ ......$
Known properties
$\gcd(a,b,c,d)=\gcd(a,b-a,c-b,d-c)$
So the problem turns into $\gcd$ Array $B, A$ The differential array of
It can be maintained by line tree

#include<bits/stdc++.h>
#define pb push_back
typedef long long ll;
using namespace std;
typedef pair<int,int> PII;
const int maxn=2e5+7;
struct gcd_tree
{
    
	int nums[maxn];
	struct tree
	{
    
		int l,r,sum;
		int mid()
		{
    
		return (l+r)/2;
		}
	}tre[maxn<<2];
	void pushup(int num)
	{
    
		tre[num].sum=__gcd(tre[2*num].sum,tre[2*num+1].sum);
	}
	void build(int num,int l,int r)
	{
    
		tre[num].l=l,tre[num].r=r;
		if(l==r)
		{
    
			tre[num].sum=nums[l];return;
		}
		int mid=tre[num].mid();
		build(2*num,l,mid);
		build(2*num+1,mid+1,r);
		pushup(num);
	}
	int query(int num,int l,int r)
	{
    
		if(tre[num].l==l && tre[num].r==r)
		return tre[num].sum;
		int mid=tre[num].mid();
		if(l>mid)
		return query(2*num+1,l,r);
		else if(r<=mid)
		return query(2*num,l,r);
		else
		return __gcd(query(2*num,l,mid),query(2*num+1,mid+1,r));
	}
}da,db;
int n,m;
int a[maxn],b[maxn];
int main()
{
    
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++) da.nums[i]=abs(a[i]-a[i-1]);
	da.build(1,1,n);
	for(int i=1;i<=n;i++) db.nums[i]=abs(b[i]-b[i-1]);
	db.build(1,1,n);
	while(m--)
	{
    
		int h1,h2,w1,w2;scanf("%d%d%d%d",&h1,&h2,&w1,&w2);
		int ans=a[h1]+b[w1];
		if(h2>h1) ans=__gcd(ans,da.query(1,h1+1,h2));
		if(w2>w1) ans=__gcd(ans,db.query(1,w1+1,w2));
		printf("%d\n",ans);
	}
}