A way to solve 1547F(#731F) by implementation

Правка en1, от handsome_gay, 2021-07-10 20:24:23

As we know, if $$$x!=1$$$ and $$$x!=y$$$, then $$$gcd(x,y)<=x/2$$$. That means for each element $$$a_i$$$ in the array, it will change at most $$$log(a_i)$$$ times before it becomes $$$1$$$.

So we can implement the process, but for every round we only consider the element that will be changed (which means $$$a_i != 1$$$ and $$$a_i != a_{i+1}$$$, then we just do $$$O(N*log(a_i))$$$ times change.

How to find the elements that will be changed in the next round? We can see that element will change in the next round, are only in the element changed in this round and their left element, so we just check them. The number of elements we check is $$$O(N*log(a_i))$$$ too.

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<string.h>
#include<set>
#include<map>
#define LL long long
#define pr pair<int,int>
#define fr first
#define sc second
//#define mp make_pair
using namespace std;
LL read( ){LL sum=0;char c=getchar( );bool f=0;while(c<'0' || c>'9') {if(c=='-') f=1;c=getchar( );}while(c>='0' && c<='9') {sum=sum*10+c-'0';c=getchar( );}if(f) return -sum;return sum;}
void read(int &sum){sum=0;char c=getchar( );bool f=0;while(c<'0' || c>'9') {if(c=='-') f=1;c=getchar( );}while(c>='0' && c<='9') {sum=sum*10+c-'0';c=getchar( );}if(f) sum=-sum;}
void read(LL &sum){sum=0;char c=getchar( );bool f=0;while(c<'0' || c>'9') {if(c=='-') f=1;c=getchar( );}while(c>='0' && c<='9') {sum=sum*10+c-'0';c=getchar( );}if(f) sum=-sum;}
const int N=500005;
int n,a[N],b[N],p[N];
int gcd(int x,int y) {return y?gcd(y, x%y):x;}
int main( )
{
  int i,x,y,L,R,T=read( );
  while(T--)
    {
      read(n);
      for(i=1;i<=n;i++) read(a[i]);
      int cnt=0, ans=0;
      for(i=1;i<=n;i++)
	{
	  x=i;
	  y=(x==n?1:x+1);
	  if(a[x]!=a[y]) p[++cnt]=x;
	}
      while(cnt)
	{
	  for(i=1;i<=cnt;i++)
	    {
	      x=p[i];
	      y=(x==n?1:x+1);
	      b[x]=gcd(a[x],a[y]);
	    }
	  set<int>S;
	  for(i=1;i<=cnt;i++)
	    {
	      x=p[i];
	      a[x]=b[x];
	    }
	  for(i=1;i<=cnt;i++)
	    {
	      x=p[i];
	      R=(x==n?1:x+1);
	      L=(x==1?n:x-1);
	      if(a[x]!=a[R] && a[x]!=1) S.insert(x);
	      if(a[L]!=a[x] && a[L]!=1) S.insert(L);
	    }
	  ans++;cnt=0;
	  for(auto &x:S) p[++cnt]=x;
	  if(!cnt) break;
	}
      printf("%d\n",ans);
    }
  return 0;
}

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en12 Английский handsome_gay 2021-07-10 23:37:23 50
en11 Английский handsome_gay 2021-07-10 23:35:28 1 Tiny change: 'q a_{i+1}$, then we ' -> 'q a_{i+1}$), then we '
en10 Английский handsome_gay 2021-07-10 23:31:33 7 Tiny change: ' y$, then $gcd(x,y)' -> ' y$, then either $gcd(x,y)'
en9 Английский handsome_gay 2021-07-10 23:31:10 16 Tiny change: ' $gcd(x,y)' -> ' $gcd(x,y)=x$ or $gcd(x,y)'
en8 Английский handsome_gay 2021-07-10 23:28:57 6 Tiny change: ' 1$ and $x>y$, then $' -> ' 1$ and $x\neq y$, then $'
en7 Английский handsome_gay 2021-07-10 23:25:20 6 Tiny change: ' 1$ and $x\neq y$, then $' -> ' 1$ and $x>y$, then $'
en6 Английский handsome_gay 2021-07-10 23:19:16 7 Tiny change: 'now, if $x!=1$ and $x\' -> 'now, if $x\neq 1$ and $x\'
en5 Английский handsome_gay 2021-07-10 23:18:54 29
en4 Английский handsome_gay 2021-07-10 20:31:28 11
en3 Английский handsome_gay 2021-07-10 20:30:02 12
en2 Английский handsome_gay 2021-07-10 20:29:06 48 Tiny change: '$ too.\n\n\n~~~~' -> '$ too.\n\n[submission:1010182]\n\n\n~~~~'
en1 Английский handsome_gay 2021-07-10 20:24:23 2399 Initial revision (published)