机试指南 cha4 数学问题
%
1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <math.h> 5 6 using namespace std; 7 // 还是A+B : 注意是末尾K位而不是第K位 8 /* 9 pow()的返回值为double类型，有时会出现返回误差 10 解决方法： 11 double x = pow(10,k); 12 int t = (int)x;// 先(int)(double(pow())) 13 */ 14 int main() 15 { 16 int a,b,k; 17 while(scanf("%d%d%d",&a,&b,&k)!=EOF) 18 { 19 if (a == 0 && b == 0) 20 break; 21 double t = pow(10,k); 22 int x = (int)t; 23 if ((a-b)%x == 0 ) 24 cout << -1 << endl; 25 else 26 cout << a+b <<endl; 27 } 28 29 return 0; 30 }
守形数
1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <math.h> 5 6 using namespace std; 7 // 守形数 8 /* 9 注意N的取值范围为2-100，故只能为低1位或者低2位 10 */ 11 int main() 12 { 13 int n ; 14 while (cin >> n) 15 { 16 int i; 17 if (n>=2 && n< 10) 18 i = 10; 19 else 20 i = 100; 21 int m = n*n; //尽量不用pow() 22 23 if ((m-n)%i == 0) 24 cout << "Yes!"<<endl; 25 else 26 cout << "No!" << endl; 27 } 28 29 return 0; 30 }
数位拆解
1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <math.h> 5 6 using namespace std; 7 /* 8 */ 9 int main() 10 { 11 long x1,x2; // 两个小于10^9的整数，保险起见用long 12 int a[15],b[15];//存放两个数的每一位数字 13 int sum; 14 int i,j; 15 while (cin >> x1 >>x2) 16 { 17 sum = 0; 18 i = 0; j = 0 ; 19 while (x1 > 0) 20 { 21 a[i++] = x1%10; 22 x1/= 10; 23 } 24 while (x2 > 0) 25 { 26 b[j++] = x2%10; 27 x2/= 10; 28 } 29 for (int i1=0;i1<i;i1++) 30 for (int j1 = 0;j1<j;j1++) 31 sum+= a[i1]*b[j1]; 32 cout <<sum << endl; 33 } 34 35 return 0; 36 }
进制转换
又一版A+B
1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <math.h> 5 6 using namespace std; 7 /* 8 */ 9 int main() 10 { 11 int m,a,b; 12 while (cin>>m>>a>>b) 13 { 14 if (m == 0) 15 break; 16 int c = a+b; 17 int size = 0;int d[10]; 18 while (c>0) 19 { 20 d[size++] = c%m; 21 c = c/m; 22 } 23 for (int i = size-1;i>=0;i--) 24 cout << d[i]; 25 } 26 27 return 0; 28 }
数制转换
1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <math.h> 5 #include <string.h> 6 7 using namespace std; 8 /* 9 */ 10 int main() 11 { 12 int a,b,a1; 13 char m[20],n[20]; 14 while (scanf("%d %s %d",&a,&m,&b)!=EOF) 15 { 16 int length = strlen(m); 17 int m1 = 0; 18 a1 = 1; // 各位初始化权重为1 19 for (int i = length-1;i>=0;i--) 20 { 21 int x; 22 if (m[i] >= '0' && m[i] <= '9') 23 x = m[i] - '0'; 24 else if (m[i] >= 'a' && m[i] <= 'z') 25 x = m[i] - 'a' + 10; 26 else if (m[i] >= 'A' && m[i] <= 'Z') 27 x = m[i] - 'A' + 10; 28 m1 += x*a1; 29 a1 *= a; 30 } 31 int size = 0; 32 while (m1>0) 33 { 34 int x = m1%b; 35 n[size++] = (x<10)?x+'0' : x-10+'A'; 36 m1 /= b; 37 } 38 for (int i =size-1;i>=0;i--) 39 cout << n[i]; 40 cout <<endl; 41 } 42 return 0; 43 }
gcd lcd
1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <math.h> 5 #include <string.h> 6 7 using namespace std; 8 /* 9 */ 10 11 int gcd(int a,int b) 12 { 13 if (b == 0) 14 return a; 15 else 16 return gcd(b,a%b); 17 } 18 int main() 19 { 20 int a,b; 21 while (cin >> a >> b) 22 { 23 cout << gcd(a,b) << endl; 24 } 25 return 0; 26 } 27 // 最小公倍数：a*b / gcd(a,b)
素数筛法
素数判定
1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <math.h> 5 #include <string.h> 6 7 using namespace std; 8 9 int judge(int n) 10 { 11 if (n ==1) 12 return 0; 13 if (n == 2) 14 return 1; 15 for (int i = 2; i <= sqrt(n)+1;i++) 16 { 17 if (n%i == 0) // i为N的一个除1和自身以外的公因数，则不是素数 18 return 0; 19 } 20 return 1; 21 22 } 23 int main() 24 { 25 int n ; 26 while (cin >> n) 27 { 28 if (judge(n)) 29 cout << "yes" <<endl; 30 else 31 cout << "no" << endl; 32 } 33 return 0; 34 }
素数
1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <math.h> 5 #include <string.h> 6 7 using namespace std; 8 // 把2-n之间所有的素数找到，在main中判断是否个位为1 9 int prime[10000]; // 存放找到的素数 10 bool isprime[10000];// 判断是否是素数 11 int primesize = 0; 12 void judge(int n) 13 { 14 for (int i = 1;i<=n;i++) 15 isprime[i] = false ; // 未判断 16 17 for (int i =2;i<n;i++) 18 { 19 // 从2开始，因为2本身就是素数 20 if (isprime[i] == true ) // 被标记成非素数 21 continue; 22 prime[primesize++] = i; // 为false时加入到prime素数数组 23 // 把素数的因数都标记为true 24 for (int j = i*i ; j<=n;j = j+i) // 为什么从i*i开始 25 isprime[j] = true; 26 27 } 28 } 29 int main() 30 { 31 int n ; 32 bool output = false; 33 while (cin >> n) 34 { 35 judge(n); 36 for (int i = 0;i<primesize;i++) 37 { 38 if (prime[i]%10 == 1) 39 { 40 if (output == false) 41 { 42 output = true; 43 cout << prime[i]; 44 } 45 else 46 cout <<" "<< prime[i]; 47 } 48 } 49 cout <<endl; 50 } 51 return 0; 52 }
Prime Number // 求1-10000内第K个素数
1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <math.h> 5 #include <string.h> 6 7 using namespace std; 8 // 把2-n之间所有的素数找到，在main中判断是否个位为1 9 int prime[100001]; // 存放找到的素数 10 int isprime[100001];// 判断是否是素数 11 int primesize = 0; 12 void judge(int n) 13 { 14 for (int i = 1;i<=n;i++) 15 isprime[i] = false ; // 未判断 16 17 for (int i =2;i<n;i++) 18 { 19 // 从2开始，因为2本身就是素数 20 if (isprime[i] == true ) // 被标记成非素数 21 continue; 22 prime[primesize++] = i; // 为false时加入到prime素数数组 23 // 把素数的因数都标记为true 24 for (int j = i*i ; j<=n;j = j+i) // 为什么从i*i开始 25 isprime[j] = true; 26 27 } 28 } 29 int main() 30 { 31 int k ; 32 judge(100000); 33 while (cin >> k) 34 { 35 cout << prime[k-1] << endl; 36 } 37 38 39 return 0; 40 }
分解素因数
考虑N的取值范围是10^9，但是如果设成10^9的数组则内存空间不足，所以仅测试1-100000内的素数是否为N的素因数，如果N很大，还有一个大于100000的素因数则加一即可，因为大于100000的素因数最多只能有一个，两个就炸了INT了。
1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <math.h> 5 #include <string.h> 6 7 using namespace std; 8 int prime[100001] ; 9 bool isprime[100001]; 10 int primesize = 0; 11 void judge(int n) 12 { 13 for (int i =0;i<=n;i++) 14 isprime[i] = false; 15 16 for (int i = 2;i<n;i++) 17 { 18 if (isprime[i] == true) 19 continue; 20 prime[primesize++] = i; 21 for (int j = i*i;j<n;j=j+i) 22 isprime[j] = true; 23 } 24 } 25 int main() 26 { 27 int n ; 28 int e[100]={0},p[100]; //存放N的质因数以及指数 29 int k = 0; 30 while (cin >> n) 31 { 32 judge(100000); 33 int number = 0 ; 34 for (int i = 0;i<primesize;i++) 35 { 36 if (n%prime[i] == 0) 37 p[k] = i; 38 else 39 continue; 40 41 while (n%prime[i] == 0) 42 { 43 e[k] ++; 44 n = n/prime[i]; 45 } 46 k++; 47 } 48 for (int i =0;i<k;i++) 49 number += e[i]; 50 if (n!=1) // N的取值范围是10^9，若测试完100000内的素数仍不能被除尽，则说明有一个大于100000的素数 51 number ++; 52 cout << number << endl; 53 54 } 55 return 0; 56 }
整除问题（超难数学题）
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h> using namespace std; int prime[1010] ; bool isprime[1010]; int primesize = 0; // 为什么是1000以内的素数？因为a的取值范围是1-1000，故a没有超过1000的素因数 // 而N！能整除a，说明N！的素因数和a的素因数必定相同 void judge(int n) { for (int i =0;i<=n;i++) isprime[i] = false; for (int i = 2;i<n;i++) { if (isprime[i] == true) continue; prime[primesize++] = i; for (int j = i*i;j<n;j=j+i) isprime[j] = true; } } int cnt[1010] ;// n!进行素因数分解后，对应prime[i]的素数的幂指数，可能为0 int cnt2[1010] ; //a的因子数 int main() { int n ,a; int k ; while (cin>> n >>a) { judge(1000); for (int i =0;i<primesize;i++) cnt[i] = cnt2[i] = 0; // 初始化两个计数器 for (int i=0;i<primesize;i++) { // 对n!分解素因数，遍历到0-1000的每一个素数, int t = n; while (t) { cnt[i]+=t/prime[i]; t = t/prime[i]; } } int ans = 100000000; for (int i=0;i<primesize;i++) { while (a%prime[i] == 0) { cnt2[i]++; a/=prime[i]; } if (cnt2[i] == 0) continue;//没有该素数则跳过,否则容易影响整除 if (cnt[i]/cnt2[i]<ans ) ans = cnt[i]/cnt2[i]; // 每计算出一个a的因数指数就和N！的比较一下 } cout <<ans <<endl; } return 0; }
二分求幂
人见人爱A^B
1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <math.h> 5 #include <string.h> 6 7 using namespace std; 8 9 int main() 10 { 11 int a,b; 12 while (cin>>a>>b) 13 { 14 if (a==0 && b==0) 15 break; 16 int ans = 1;//最终结果变量 17 while (b!=0) 18 { 19 if (b%2==1) 20 { 21 ans *= a; // ans 累乘a 22 ans%=1000; // ans仅取后三位 23 } 24 b/=2; 25 a = a*a;//求下一位二进制位的权重 26 a %= 1000;//求a的后三位 27 } 28 cout << ans << endl; 29 } 30 return 0; 31 }
A sequence of numbers
10 min
1 #include<stdio.h> 2 #define ret 200907 3 long long cal(long long a,long long q,int k){ 4 long long ans=a; 5 k--; 6 while( k > 0){ 7 if(k%2==1){ 8 ans = (ans * q) % ret; 9 } 10 k/=2; 11 q= (q*q)%ret; 12 } 13 return ans; 14 } 15 int main(){ 16 int n; 17 scanf("%d",&n); 18 for(int i=0;i<n;i++){ 19 long long a,b,c,ans; // a,b,c取值范围为0-2^64，long long 为64位的 20 int k; // 10^9 int 足矣 21 scanf("%lld%lld%lld%d",&a,&b,&c,&k); 22 if(b-a==c-b) 23 ans=(a%ret+(k-1)*((b-a)%ret))%ret; // (a+b)%c = (a%c +b%c)%c ,防止（a+b)溢出问题 24 else{ 25 long long q=b/a; 26 ans=cal(a,q,k); 27 } 28 printf("%lld ",ans); 29 } 30 return 0; 31 }
高精度整数
a+b
超开心的是这道题我独立做出来了！虽然耗时很久，但自己思考比不停看别人的代码要强的多！
1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <math.h> 5 #include <string.h> 6 7 using namespace std; 8 9 /* 10 a + b 位数不超过1000位，大整数，不能用基本数据类型存储，必须用字符串或者数组的形式 11 12354484 324645 12 time : 20+20+20+20+20 = 1h 45 min 13 14 笔记： 15 1. 数组的初始化方式： 16 int b[10]={0}; 17 但是如果是： int b[10] = {1} , 却只有第一个元素被初始化为1，其余仍为0 18 19 或者： 20 int a[size] ; 21 memset(a,0,sizeof(int)*size); 对某指针指向的内存进行赋值，全部赋值为0 22 23 2. 结构体的初始化方式： 24 X x1 = { 1,2.2, 'c' }; 25 X x2[3] = { {1, 1.1, 'a'}, {2, 2.2, 'b'}}; 使用大括号中嵌套大括号的方式 26 27 3. 对齐输出0000 28 %0xd // x为输出的整数宽度 29 30 */ 31 struct bigInteger { 32 int digit[300]; 33 int size; // 该大整数的位数 34 }; // 每四位数字保存到一个数组里 35 36 int cal(char s1[1010],int i,int n) 37 { 38 // s1[i] - s1[i-n+1]变为整数,循环N次 39 int ans = 0; 40 int r = 1; 41 for (int j=0;j<n;j++) 42 { 43 ans += (s1[i]-'0')*r; 44 i--; 45 r *= 10; 46 } 47 return ans; 48 } 49 50 void print(bigInteger a) 51 { 52 // 输出的要求很严格：非第一个数组则补齐四位 53 printf("%d",a.digit[a.size-1]); 54 for (int i = a.size-2;i>=0;i--) 55 { 56 printf("%04d",a.digit[i]); 57 } 58 cout << endl; 59 60 } 61 void init(bigInteger &a,char s[],int len) 62 { 63 int i; 64 if (len >= 4) 65 { 66 for (i = len-1;i>=3;i = i-4) 67 a.digit[a.size++] = cal(s,i,4); 68 // 如果字符串不正好是4的倍数，开头剩余必小于4 69 if (i!=-1) 70 { 71 a.digit[a.size++] = cal(s,i,i+1); 72 } 73 } 74 else 75 a.digit[a.size++] = cal(s,len-1,len); 76 } 77 int main() 78 { 79 bigInteger a={{0},0},b = {{0},0},c = {{0},0}; 80 int i; 81 /* 1. 如何把很长的字符串输入到数组中 82 输入到两个字符数组中，从size-1开始每四位字符形成一个整数，存放到数组中， 83 从0开始倒着往数组中放，输出的时候从size反着输出即可 84 */ 85 char s1[1010],s2[1010]; 86 int len1,len2; 87 while (scanf("%s %s",s1,s2)!=EOF) 88 { 89 // 初始化为0，这样后面的相加部分才不用分长短讨论 90 a={{0},0};b = {{0},0};c = {{0},0}; 91 len1 = strlen(s1); 92 len2 = strlen(s2); 93 init(a,s1,len1); 94 init(b,s2,len2); 95 // 把两部分相加，从数组0号开始递增，大于10000，截断第五位，加到下一个数组 96 int add = 0,len = (a.size >= b.size) ? a.size : b.size;// 进位 97 for (i = 0;i<len;i++) 98 { 99 int temp = a.digit[i] + b.digit[i] + add; 100 add = temp/10000; 101 c.digit[c.size++] = temp%10000; 102 } 103 // print(a); 104 // print(b); 105 print(c); 106 107 } 108 109 return 0; 110 }
N的阶乘
39 min
1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <math.h> 5 #include <string.h> 6 #include <algorithm> 7 8 using namespace std; 9 10 struct bigInteger 11 { 12 int digit[1001]; // 1000 ! < 1000^1000,每四位存储一个 13 int size; // digit的长度 14 }a = {{0},0}; 15 16 void print() 17 { 18 // 找到不为0的第一位 19 for (int i = 1 ;i<=1001;i++) 20 { 21 if (a.digit[i]!=0 && a.digit[i+1] == 0) 22 { 23 a.size = i; 24 break; 25 } 26 27 } 28 // i 指向最后一位 29 30 printf("%d",a.digit[a.size]); 31 for (int i = a.size-1; i >=1 ;i--) 32 printf("%04d",a.digit[i]); 33 cout << endl; 34 } 35 int main() 36 { 37 int n; 38 while (cin>>n) 39 { 40 a = {{0},0}; 41 int c = 0; 42 a.digit[++a.size] = 1; // digit 从size=1 开始记录 43 for (int i = 2 ;i<=n;i++) 44 { 45 for (int j = 1;j<=1000;j++) // digit数组中的每个元素都要乘以乘数 46 { 47 a.digit[j] = (a.digit[j]*i + c); 48 int temp = a.digit[j]; 49 c = a.digit[j]/10000; 50 a.digit[j] %= 10000; 51 // size什么时候增加？每一位可能会产生无数次向前的进位 52 } 53 } 54 print(); 55 } 56 57 return 0; 58 }
浮点数加法
1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <math.h> 5 #include <string.h> 6 #include <algorithm> 7 8 using namespace std; 9 10 /* 11 浮点数从小数点进行分割，一个字符串分割成整数和小数数组， 12 但小数是左对齐，整数是右对齐。加完小数之后的进位和整数相加 13 */ 14 15 struct bigInteger 16 { 17 int digit[1001]; 18 int size; 19 int point; 20 }a,b,c; 21 22 int cal(char s[],int i,int n) 23 { 24 int sum = 0; 25 int c = 1; 26 for (int j = 0 ; j < n ;j++) 27 { 28 sum += (s[i--]-'0')*c; 29 c *= 10; 30 } 31 return sum; 32 } 33 void init(char s[],bigInteger &a) 34 { 35 int len = strlen(s); 36 // 找到小数点，记录位置并删除 37 int i; 38 for (i = 0;i<len;i++) 39 { 40 if (s[i] == '.') 41 { 42 a.point = i; 43 break; 44 } 45 } 46 for (i; i < len;i++) 47 { 48 s[i] = s[i+1]; 49 } 50 for (i = len-2; i >= 3 ;i -= 4) 51 { 52 a.digit[++a.size] = cal(s,i,4); 53 } 54 if (i != -1) 55 { 56 // 不是4的倍数 57 a.digit[++a.size] = cal(s,i,i+1); 58 } 59 } 60 void print(bigInteger a) 61 { 62 int i; 63 printf("%d",a.digit[a.size]); 64 for (i = a.size-1 ; i >=1 ;i--) 65 { 66 printf("%04d",a.digit[i]); 67 } 68 cout << endl; 69 } 70 int main() 71 { 72 int len1,len2,len; 73 char s1[1001],s2[1001]; 74 while (scanf("%s %s",s1,s2)!=EOF) 75 { 76 // 初始化biginteger结构体 77 init(s1,a); 78 init(s2,b); 79 80 print(a); 81 print(b); 82 83 } 84 85 86 return 0; 87 }
二分求幂 问题重做 20min
过程推演了一会儿，代码的编写比较简单，主要是把过程弄懂
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include <queue> 6 #include <vector> 7 8 using namespace std; 9 10 11 12 int main() 13 { 14 int a,b; 15 while (cin>>a>>b) 16 { 17 if (a == 0 && b == 0) 18 break; 19 int ans = 1; int r = 0; // b对2的余数 20 int t = a; // a的平方 21 while (b>0) 22 { 23 r = b%2; 24 b = b/2; 25 26 if (r == 1) 27 { 28 ans = (ans * t)%1000; 29 } 30 t = (t*t)%1000; 31 } 32 cout << ans << endl; 33 34 } 35 36 return 0; 37 }
Tr
1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 5 using namespace std; 6 const int ret = 9973; 7 void cal(int a[11][11],int b[11][11],int n,int c[][11]) 8 { 9 10 int i,j,k; 11 for (i=1;i<11;i++) 12 for (j=1;j<11;j++) 13 c[i][j] = 0; 14 for (i = 1 ; i<=n;i++) 15 { 16 for (j=1;j<=n;j++) 17 { 18 for (k = 1 ; k <= n ;k++) 19 { 20 c[i][j] += a[i][k]*b[k][j]; 21 } 22 23 } 24 } 25 } 26 void equal(int ans[][11],int tmp[][11]) 27 { 28 int i,j; 29 for (i=1;i<11;i++) 30 for (j=1;j<11;j++) 31 { 32 ans[i][j] = tmp[i][j]; 33 } 34 } 35 int main() 36 { 37 int t,i,j,n,k,z; 38 int a[11][11]; 39 while (cin >> t) 40 { 41 for (z = 0;z<t;z++) 42 { 43 cin >> n >> k; 44 for (i = 1;i<n+1;i++) 45 for (j = 1;j<n+1;j++) 46 cin >> a[i][j]; 47 48 int ans[11][11] = 49 {1,0,0, 50 0,1,0, 51 0,0,1 52 }; 53 int tmp[11][11]; 54 while (k>0) 55 { 56 if (k%2 == 1) 57 { 58 cal(ans,a,n,tmp); 59 equal(ans,tmp); 60 } 61 k = k/2; 62 //a = a * a; 63 cal(a,a,n,tmp); 64 equal(a,tmp); 65 } 66 int c = 0; 67 for (i = 1 ;i<=n;i++) 68 { 69 c += ans[i][i]; 70 } 71 cout << c <<endl; 72 } 73 } 74 return 0 ; 75 }