codeforces 数论分析题

题目：http://codeforces.com/contest/359/problem/C

 

题意：给一个素数x和一个长度为n的数列a[]，求的分子和分母的最大公约数。

 

分析：对于分子来说，我们把分子中的每一相等的项合并起来，然后相同的项必然有系数，那么所有的系数有可能也是x的倍

数。那么我们把它提出来即可。

#include <iostream> #include <string.h> #include <stdio.h> #include <math.h> #include <map>using namespace std; typedef long long LL; const LL N = 100005; const LL MOD = 1000000007;LL n,x; LL a[N]; map<LL,LL> w;LL quick_mod(LL a,LL b,LL m) {LL ans = 1;a %= m;while(b){if(b&1){ans = ans * a % m;b--;}b >>= 1;a = a * a % m;}return ans; }int main() {LL s = 0;w.clear();scanf("%I64d%I64d",&n,&x);for(int i=0;i<n;i++){scanf("%I64d",&a[i]);s += a[i];w[a[i]]++;}int i = a[n-1];while(w[i] % x == 0){w[i-1] += w[i] / x;--i;}if(i < 0) i = 0;printf("%I64d\n",quick_mod(x,s-i,MOD));return 0; }

 

总结

以上是生活随笔为你收集整理的codeforces 数论分析题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。