小明系列故事——师兄帮帮忙

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 3699    Accepted Submission(s): 965
Problem Description 　　小明自从告别了ACM/ICPC之后，就开始潜心研究数学问题了，一则可以为接下来的考研做准备，再者可以借此机会帮助一些同学，尤其是漂亮的师妹。这不，班里唯一的女生又拿一道数学题来请教小明，小明当然很高兴的就接受了。不过等他仔细读题以后，发现自己也不会做，这下小明囧了：如果回复说自己不懂，岂不是很没面子？
　　所以，他现在私下求你帮忙解决这道题目，题目是这样的：
　　给你n个数字，分别是a1,a2,a3,a4,a5……an，这些数字每过一个单位时间就会改变，假设上一个单位时间的数字为a1’,a2’,a3’……an’，那么这个单位时间的数字a[i] = a[i - 1]’ * K(i == 1的时候a[1] = a[n]’ * K)，其中K为给定的系数。
　　现在的问题就是求第t单位时间的时候这n个数字变成了什么了？由于数字可能会很大，所以只要你输出数字对10^9 + 7取余以后的结果。
  Input 　　输入数据第一行是一个正整数T，表示有T组测试数据；
　　每组数据有两行，第一行包含输入三个整数n, t, k，其中n代表数字个数，t代表第t个单位时间，k代表系数；第二行输入n个数字ai，代表每个数字开始的时候是多少。

　　[Technical Specification]
　　T <= 100
　　1 <= n <= 10 ^ 4
　　0 <= t <= 10 ^ 9　　其中 t = 0 表示初始状态
　　1 <= k <= 10 ^ 9
　　1 <= ai<= 10 ^ 9
  Output 　　对于每组数据请输出第t单位时间后这n个数字变成了什么，输出的时候每两个数字之间输出一个空格，行末不要输出多余的空格，具体见样例。   Sample Input 2 3 2 5 1 2 3 3 0 5 1 2 3   Sample Output 50 75 25 1 2 3   Source 2013腾讯编程马拉松初赛第一场（3月21日）   Recommend liuyiding   |   We have carefully selected several similar problems for you:  4822 4821 4820 4819 4818    思路： 由上面的一次递推式：a[i] = a[i - 1]’ * k，那么经过t次迭代可知，公式可以变成a[i+t] = a[i ]’ * k^t % mod,把0 - n-1看成一个圆环， 每次t个数更新一个值，0->t,1->t+1,........n-t -> n , n->t,则经过n次迭代，就可以完成．这里的k^t%mod可以用pow()函数完成，不过会超时， 这里刚好可以用蒙哥马利算法－求快速幂：http://blog.csdn.net/linraise/article/details/17490769求k^t % mod．剩下的就很容易解决． //A(i+t) = A(i)* k^t % 1e9+7 #include #include using namespace std; __int64 A,B[10005]; __int64 T,n,t,k,i; __int64 mod = 1000000007; __int64 Montgomery(__int64 base,__int64 exp) { __int64 res = 1; while(exp) { if (exp&1) // if is odd res = (res*base) % mod; exp >>= 1; base = (base*base) % mod; } return res; } int main() { cin >> T; while(T--) { cin >> n >> t >> k; k = Montgomery(k,t); for(i=0; i < n; ++i) { cin >> A; B[(i+t)%n] = ((A% mod)* (k % mod)) % mod; } for(i=0; i < n-1; ++i) cout << B[i] << ' '; cout << B[i] << endl; } return 0; } http://acm.hdu.edu.cn/showproblem.php?pid=1211

RSA

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1179    Accepted Submission(s): 863
Problem Description RSA is one of the most powerful methods to encrypt data. The RSA algorithm is described as follow:

> choose two large prime integer p, q
> calculate n = p × q, calculate F(n) = (p - 1) × (q - 1)
> choose an integer e(1 < e < F(n)), making gcd(e, F(n)) = 1, e will be the public key
> calculate d, making d × e mod F(n) = 1 mod F(n), and d will be the private key

You can encrypt data with this method :

C = E(m) = me mod n

When you want to decrypt data, use this method :

M = D(c) = cd mod n

Here, c is an integer ASCII value of a letter of cryptograph and m is an integer ASCII value of a letter of plain text.

Now given p, q, e and some cryptograph, your task is to "translate" the cryptograph into plain text.
  Input Each case will begin with four integers p, q, e, l followed by a line of cryptograph. The integers p, q, e, l will be in the range of 32-bit integer. The cryptograph consists of l integers separated by blanks. 
  Output For each case, output the plain text in a single line. You may assume that the correct result of plain text are visual ASCII letters, you should output them as visualable letters with no blank between them.
  Sample Input 101 103 7 11 7716 7746 7497 126 8486 4708 7746 623 7298 7357 3239   Sample Output I-LOVE-ACM.   Author JGShining（极光炫影）   Source 杭电ACM省赛集训队选拔赛之热身赛   思路： 　　经典的RSA加密解密算法的实现，其中，蒙哥马利算法的一个最经典的实现就是用在RSA中，解密的c^d%n可以用快速幂模的方法，其余部分都很容易理解。 #include using namespace std; //base^exp % mod,蒙哥马利 __int64 base, exp, mod, p, q, e, l, Fn; __int64 Modul(__int64 base, __int64 exp, __int64 mod) { __int64 ans = 1; while (exp) { if (exp&1) ans = (ans*base) % mod; exp >>= 1; base = (base*base) % mod; } return ans; } int main() { // freopen("2.txt","r",stdin); while(cin>>p>>q>>e>>l) { mod = p*q; Fn = (p-1)*(q-1); exp = 1; while ((exp*e) % Fn != 1) ++exp; while(l--) { cin >> base; printf("%c",Modul(base,exp,mod)); } puts(""); } //cout << Modul() << endl; return 0; }

HDU1575-Tr A

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2219    Accepted Submission(s): 1652
Problem Description A为一个方阵，则Tr A表示A的迹（就是主对角线上各项的和），现要求Tr(A^k)%9973。 Input 数据的第一行是一个T，表示有T组数据。
每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行，每行有n个数据，每个数据的范围是[0,9]，表示方阵A的内容。 Output 对应每组数据，输出Tr(A^k)%9973。 Sample Input 2 2 2 1 0 0 1 3 99999999 1 2 3 4 5 6 7 8 9 Sample Output 2 2686 Author xhd   思路： 　　　典型的快速矩阵幂模的例子，只需要将上面的蒙哥马利的1换成单位矩阵，base换成矩阵结构体，乘法换成矩阵乘法即可。
#include #include #include using namespace std; const int MAX = 11; int exp; //base^exp % mod int n; struct Matrix { int matrix[MAX][MAX]; }; Matrix Base; Matrix MatrixMul(const Matrix& x,const Matrix& y) { Matrix z; memset(z.matrix,0,sizeof(z.matrix)); int i, j, k; for (i=0; i < n; ++i) { for (j=0; j < n; ++j) { for (k=0; k < n; ++k) { z.matrix[i][j] += x.matrix[i][k]*y.matrix[k][j]; z.matrix[i][j] %= 9973; } } } return z; } Matrix QuickMod(Matrix& x,int exp) { int i; Matrix ans; //单位矩阵 memset(ans.matrix,0,sizeof(ans.matrix)); for (i=0; i < n; ++i) ans.matrix[i][i] = 1; while (exp) { if (exp&1) ans = MatrixMul(x,ans); x = MatrixMul(x,x); exp >>= 1; } return ans; } int main() { #ifndef ONLINE_JUDGE freopen("2.txt","r",stdin); #endif int T, i, j, sum; cin >> T; while (T--) { cin >> n >> exp; for (i=0; i < n; ++i) { for (j=0; j < n; ++j) { cin >> Base.matrix[i][j]; Base.matrix[i][j] %= 9973; } } Base = QuickMod(Base,exp); sum = 0; for (i=0; i < n; ++i) sum += Base.matrix[i][i]; cout << sum % 9973<< endl; } return 0; }