SPOJ BLAMOEBA - Super Amoeba
题目链接：http://www.spoj.com/problems/BLAMOEBA/
题目大意：有一种叫做阿米巴的虫子一天能分裂成M个虫子。现有X个这种虫子，从第一天开始进行分裂，每次分裂之后就取走Y个，问如果要第N天取走之后不再有虫子剩余，并且X尽可能小，那么X和Y应该为多少。2<M<100000 ,1<N<100000
解题思路：分析后可以得到 (mn-1)Y = mn(m-1)X. 那么关键就是对这个式子两边约分，当X,Y两个系数互素的时候就是答案了。如何约分呢？首先考虑 mn-1 与 m-1 的关系。
m % (m-1) = 1 ----> mn % (m - 1) = 1 ----> (mn- 1) % (m - 1) = 0. 所以，左右两边可以同时除以 m - 1。之后，由于 mn - 1 可以分解为 (m - 1) * (a1mn-1+ a2mn-2+...+am + 1) ，因此除以 m - 1 之后两者已经互素。
接下来就可以利用快速幂取模以及逆元来求X，Y对应的值了。
代码：
1 ll n, m; 2 3 ll ext_gcd(ll a, ll b, ll &d, ll &x, ll &y){ 4 if(b) { 5 ext_gcd(b, a % b, d, y, x); y -= x * (a / b); 6 } 7 else{ 8 d = a; x = 1; y = 0; 9 } 10 } 11 ll pow_mod(ll a, ll b){ 12 if(b == 0) return 1; 13 ll tmans = pow_mod(a, b / 2); 14 ll ans = tmans * tmans % mod; 15 if(b & 1) ans = a % mod * ans; 16 return ans % mod; 17 } 18 void solve(){ 19 ll up = pow_mod(m, n); 20 ll x, y, d; 21 ext_gcd(m - 1, mod, d, x, y); 22 if(x < 0) x = (abs(x) / mod + 1) * mod + x; 23 ll dn = (up - 1) * x % mod; 24 printf("%lld %lld\n", dn, up); 25 } 26 int main(){ 27 int t; 28 scanf("%d", &t); 29 while(t--){ 30 scanf("%lld %lld", &m, &n); 31 solve(); 32 } 33 }
题目：
BLAMOEBA - Super Amoeba
Peter has an amoeba farm with pretty much unlimited amoebae. After years of research, Peter created a device to convert some amoebae to super amoebae. However, his device can only be used once. Every day, a super amoeba will split into M super amoebae (2<M<100000).
Now, Peter plan his amoeba selling business. Initially, Peter converts X amoebae to super amoebae (X>1). Every day after the amoebae split, Peter will take Y super amoebae for sale (Y>1). After N days, Peter want all of his amoebae to be completely sold out (1<N<100000). Since the energy needed to convert amoebae is quite massive, X must be as small as possible. Help peter plan his business!
Input
First line is T, number of test cases (T<100000). Next T lines each contains M and N separated by space.
Output
For each case, output X and Y separated by space. Since X and Y can be very large, output them with modulo 1000000007.
Example
Input: 1
4 3 Output: 21 64
Explanation
Initially, Peter has 21 super amoebae.
After day 1, there are 4 x 21 - 64 = 20 super amoebae
After day 2, there are 4 x 20 - 64 = 16 super amoebae
After day 3, there are 4 x 16 - 64 = 0 super amoeba
All the super amoebae are sold out after the 3rd day just as planned.
1、python 链接mysql
2、Junit白盒测试条件组合覆盖
3、sqlalchemy.exc.InternalError: (pymysql.err.InternalError) (1091, "Can't DROP 'users_ibfk_1'; check that column/key exists") [SQL: ALTER TABLE users DROP FOREIGN KEY users_ibfk_1]
4、SharePoint Column Format
5、数据结构--队列