Posted on 2011-10-08 21:32
Uriel 阅读(1063)
评论(5) 编辑 收藏 引用 所属分类:
考研&保研复试上机题
难度还行。。
明天机试+面试。。各种紧张中。。向众神、众大牛求光环。。Orz
1. 特殊乘法
水题不解释
//2010年清华大学计算机研究生机试题 特殊乘法
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int ans;
char a[20], b[20];
int main() {
int l1, l2, i, j;
while(~scanf("%s %s", a, b)) {
l1 = strlen(a);
l2 = strlen(b);
ans = 0;
for(i = 0; i < l1; ++i) {
for(j = 0; j < l2; ++j) {
ans += (a[i] - '0') * (b[j] - '0');
}
}
printf("%d\n", ans);
}
return 0;
}
2. 整数拆分
找规律
//2010年清华大学计算机研究生机试题 整数拆分
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MOD 1000000000
int f[1000010];
int main() {
int i;
f[1] = 1; f[2] = 2;
for(i = 3; i <= 1000000; ++i) {
if(i & 1) f[i] = f[i - 1];
else
f[i] = (f[i - 1] + f[i >> 1]) % MOD;
}
while(~scanf("%d", &i)) printf("%d\n", f[i]);
return 0;
}
3. 求root(N, k)
感谢光神指点 Orz
方法就是用模取幂模板(Orz..天哥模板)，注意是求a^b%(k-1)，如果a^b%(k-1)==0，则输出k-1，否则输出a^b%(k-1)~
//2010年清华大学计算机研究生机试题 求root(N, k)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define I long long
I x, y, tp;
int m, k;
I mod_exp(I a, I b) {
I ans = 1;
while(b) {
if(b & 1) ans = ans * a % m;
a = a * a % m;
b >>= 1;
}
return ans;
}
int main() {
while(~scanf("%lld %lld %d", &x, &y, &k)) {
m = k - 1;
tp = mod_exp(x, y);
if(!tp) printf("%d\n", m);
else
printf("%lld\n", tp);
}
return 0;
}