Codeforces Round #505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final) -B C(GCD，最长连续交替序列)

During the research on properties of the greatest common divisor (GCD) of a set of numbers, Ildar, a famous mathematician, introduced a brand new concept of the weakened common divisor (WCD) of a list of pairs of integers.

For a given list of pairs of integers 1, such that it divides at least one element in each pair. WCD may not exist for some lists.

For example, if the list looks like 1 and divides at least one number in each pair).

You're currently pursuing your PhD degree under Ildar's mentorship, and that's why this problem was delegated to you. Your task is to calculate WCD efficiently.

Input

The first line contains a single integer 1≤n≤150000) — the number of pairs.

Each of the next 2≤ai,bi≤2⋅109).

Output

Print a single integer — the WCD of the set of pairs.

If there are multiple possible answers, output any; if there is no answer, print −1.

Examples

input

Copy

output

Copy

input

Copy

2
10 16
7 17

output

Copy

-1

input

Copy

output

Copy

Note

In the first example the answer is 12 from the third ones. Note that other valid answers will also be accepted.

In the second example there are no integers greater than 1 satisfying the conditions.

In the third example one of the possible answers is 15 is also allowed, but it's not necessary to maximize the output.

$5$

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,n;
ll gcd(ll x,ll y){return x%y? gcd(y,x%y):y;}
int main(){
    cin>>n;
    cin>>a>>b;
    for(int i=1;i<n;++i){
        ll x,y;cin>>x>>y;
        x*=y;a=gcd(a,x);b=gcd(b,x);
    }
    if(a==1&&b==1){cout<<"-1
";return 0;}
    for(ll i=2;i*i<=a||i*i<=b;++i)
        if(a%i==0||b%i==0){cout<<i<<endl;return 0;}
    if(a!=1)cout<<a<<endl;
    else cout<<b<<endl;
    return 0;
}

　方法2.

把第一对数的所有因子提出来然后对后面的每一对数进行测试，如果后面每一对数中只是有一个可以被因子可以整除，则输出因子。

代码：

#include<bits/stdc++.h>
int n,a[150010],b[150010],p[100],c;
void d(int x){
    for(int i=2;1ll*i*i<=x;i++)if(x%i==0){
        p[c++]=i;
        while(x%i==0)x/=i;
    }
    if(x>1)p[c++]=x;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d%d",a+i,b+i);
    d(a[0]);
    d(b[0]);
    for(int i=0;i<c;i++){
        bool fl=1;
        for(int j=0;j<n&&fl;j++)if(a[j]%p[i]!=0&&b[j]%p[i]!=0)fl=0;
        if(fl){
            printf("%d
",p[i]);
            return 0;
        }
    }
    puts("-1");
}

C. Plasticine zebra
http://codeforces.com/contest/1025/problem/C
题目大意：输出一个字符串中最长“斑马条纹”的长度，“斑马条纹”指类似于“wbwbwbw”（7）、“bwbwb”（5）。
同时为了最终获得更长的长度，可以在组装斑马之前，Grisha可以进行以下操作0或更多次。他将序列在某个地方分成两部分，然后将它们中的每一部分反转并再次将它们粘在一起。例如，如果Grisha的顺序为“ bwbbw ”（这里' b '表示黑条，' w '表示白条），那么他可以将序列拆分为bw | bbw（此处垂直条代表切割），反转两个部分并获得“ wbwbb ”。

例如
input:
bwwwbwwbw
output:
5

备注：在第一个例子中，可能的操作顺序之一是bwwbww | bw → w | wbwwwbwb → wbwbw wwbw，给出的答案等于5。

思路：
从样例一中逆推，发现最后得到的斑马条纹其实始终来自序列的两侧，经过操作后拼接在一起，于是我们可以直接将两个s拼接在一起，创造出一个2s，此时找出2s中的最长斑马条纹即可。
但要注意最长长度不会超过s的长度，就错在这里没有过fst。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod=1e9+7;
const int maxn=1e7+50;
const ll inf=0x3f3f3f3f3f3f;
int k;
ull gcd(ull a,ull b)
{
    while(b)
    {
        int t=a%b;
        a=b;
        b=t;
    }
    return a;
}
ull lcm(ull a,ull b){
    return a/gcd(a,b)*b;
}
ull sum[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    string s;
    int num=1,maxnum=0;
    cin>>s;
    s=s+s;
    for(int i=1;i<s.size();i++)
    {
        if(s[i]!=s[i-1])
        {
            num++;
        }
        else{
            num=1;
        }
        if(num>maxnum)
        {
            maxnum=num;
        }
    }
    int k=s.size();
    cout<<min(maxnum,k/2)<<endl;
    return 0;
}

Codeforces Round #505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final) -B C(GCD，最长连续交替序列)

相关推荐