Posted on 2011-10-08 21:32
Uriel 閱讀(1093)
評論(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;
}