Prime Number(CodeForces-359C)【快速幂/思维】

题意：已知X，数组arr[n],求一个分式的分子与分母的最大公因数。分子为ΣX^arr[i],分母为X^Σarr[i]，数组为不递减序列。

思路：比赛的时候以为想出了正确思路，WA掉了很多发，看了别人写的代码才发现自己漏掉很多细节。

　　1.容易想到，分子的最低次幂即可能为所需答案

　　2.由于arr里存在相同的数，因此分子的各个幂存在可以合并同类项的情况，所以应该先彻底完成合并同类项，再进行步骤1。

　　3.一个小技巧，并不需要完成所有项的合并，当且仅当当前最小项的系数可以被X整除时才需要继续合并，否则当前项的次数即为答案所需次数。

特别需要注意的是：完成合并后，分子的最低次幂的次数是有可能大于分母的次数的，所以应该取二者的较小值作为答案的次数。

代码如下：

#include<cstdio>

#include<iostream>

using namespace std;

const int mo=1e9+;

int x;

int mpow(long long xx,long long nn){

    long long res=;

    while(nn!=){

        if(nn&){

            res=res*xx%mo;

        }

        nn>>=;

        xx=xx*xx%mo;

    }

    return res;

}

int main(){

    int n;

    long long num=,arr[];

    scanf("%d%d",&n,&x);

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

        scanf("%I64d",&arr[i]);

        num+=arr[i];

    }

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

        arr[i]=num-arr[i];

    }

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

        swap(arr[i],arr[n-i+]);

    }

    int sum=;

    long long ans;

    arr[n+]=-;

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

        if(arr[i]==arr[i-]){

            sum++;

        }

        else {

            if(sum%x==){

                sum/=x;

                arr[--i]++;

            }

            else {

                ans=arr[i-];

                break;

            }

        }

    }

    ans=min(ans,num);

    printf("%d",mpow(x,ans));

    return ;

}

By xxmlala

巴特西

Prime Number(CodeForces-359C)【快速幂/思维】

最新文章

热门文章