首页 / 软件开发 / 数据结构与算法 / 给一个素数 求s和t的最大公约数

给一个素数 求s和t的最大公约数2015-02-15题目链接：http://codeforces.com/contest/359/problem/C

题意：

给一个素数x，和a1、a2……an，计算这个式子 的时候，化成了 这个形式, 且t等于 xa1+a2+...+an，求s和t的最大公约数

（1≤n≤105, 2≤x≤109） ，结果对1000000007 取模

分析：

直接分析s和t，并不能想到如何求gcd，那我们可以想一下，gcd和什么有关系：分子分母同除以gcd就可以得到最简分式，我们可以从这里入手

题目中给定了a的顺序，那么想一下通常我们计算这样的分式的方法：首先分母都能化成 xan ，分子为x ^ （an - a1）、x ^ （an - a2）的形式。

这时候考虑是否能通分，需要先明白这个问题：sigma（x ^ k） + 1（k  >= 1） 是不能被x整除的，因为一个加数可以被x整除，1显然不行，所以整体不行。那么，考虑通分的时候，如果最后的1的个数不能达到x的整数倍，整体就是不可通分的，关键也就是在处理这里。

另外说一下自己没有想到的问题：对于（x * x ）/ x这样的式子，最大公约数是x而不能是x * x。在计算通分的时候需要额外注意

const int MOD = 1000000007; const int MAXN = 110000;LL ipt[MAXN];LL qkpow（LL a, LL b） { LL ret = 1; while （b） { if （b & 1） ret = ret * a % MOD; b >>= 1; a = a * a % MOD; } return ret; }int main（） { //freopen（"in.txt", "r", stdin）; LL n, x; while （cin >> n >> x） { map<LL, LL> mp; map<LL, LL>::iterator it;LL sum = 0; FE（i, 1, n） { cin >> ipt[i]; sum += ipt[i]; } FE（i, 1, n） { mp[ipt[n] - ipt[i]]++; } while （true） { it = mp.begin（）; LL a = it->first, b = it->second; if （b % x == 0） { while （b % x == 0） { b /= x; a++; } mp.erase（it）; mp[a] += b; } else break; } cout << qkpow（x, sum - ipt[n] + min（ipt[n], mp.begin（）->first）） << endl; } return 0; }