Avito Cool Challenge 2018 :E. Missing Numbers

E. Missing Numbers

题目链接：https://codeforces.com/contest/1081/problem/E

题意：

现在有n个数（n为偶数），但只给出a2,a4....an的信息，要求你求出a1,a2....an。

假设前n项的和为Sn,那么满足S1,S2....Sn都为平方项。

题解：

假设S1=a^2，S2=b^2，S3=c^2，S4=d^2，因为我们已知a2,a4，所以得出a2=S2-S1=b^2-a^2，a4=d^2-c^2。

我们可以根据我们设的未知数推出a1=a^2,a3=c^2-b^2。

最后我们将这个推广可以推出a1,a3....an-1的表达式可以根据a0,a2...an得出，这里我们令a0=0。

现在的任务就是找每个数的因子，因为b^2-a^2=(b+a)*(b-a)。这里我们直接预处理一下就好了~

然后我们维护一下之前那个数的b^2（较大平方项），在找当前这个数的c^2（较小平方项），根据这个相减就可以求出他们中间的ai了~

代码如下：

#include <bits/stdc++.h>

#define mx 2e5

using namespace std;

typedef long long ll;

const int N =2e5+;

ll a[N];

int n;

vector <int> Div[N];

int main(){

    cin>>n;

    for(int i=;i<=n;i+=) scanf("%I64d",&a[i]);

    for(int i=;i<=mx;i++)

        for(int j=i;j<=mx;j+=i) Div[j].push_back(i); //nlogn预处理

    ll last = ;

    for(int i=;i<=n;i+=){

        ll mn=2e18;

        for(auto v:Div[a[i]]){

            int d=a[i]/v;

            if(d%==v%){

                ll now = (max(d,v)-min(d,v))/;

                if(now*now>last)

                mn = min(mn,now*now);

            }

        }

        if(mn==2e18){

            puts("No");return ;

        }

        a[i-]=mn-last;

        last = a[i]+mn;

    }

    puts("Yes");

    for(int i=;i<=n;i++){

        printf("%I64d ",a[i]);

    }

    return ;

}

巴特西

Avito Cool Challenge 2018 :E. Missing Numbers

最新文章

热门文章