devbox
小舞很执着
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【算法笔记自学】第 5 章 入门篇（3）——数学问题

作者：小舞很执着 | 2024-07-13 04:13:59

赞

踩

【算法笔记自学】第 5 章 入门篇（3）——数学问题

5.1简单数学

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4. bool cmp(int a,int b){
  5.      return a>b;
  6. }
  7. void to_array(int n,int num[]){
  8.     for(int i=0;i<4;i++){
  9.         num[i]=n%10;
  10.         n /=10;
  11.      }
  12. }
  13. int to_number(int num[]){
  14.     int sum=0;
  15.     for(int i=0;i<4;i++){
  16.         sum=sum*10+num[i];
  17.     }
  18.     return sum;
  19. }
  20. int main(){
  21.     int n,MIN,MAX;
  22.     scanf("%d",&n);
  23.     int num[5];
  24.     while(1){
  25.        to_array(n,num);
  26.        sort(num,num+4);
  27.        MIN=to_number(num);
  28.        sort(num,num+4,cmp);
  29.        MAX=to_number(num);
  30.        n=MAX-MIN;
  31.        printf("%04d-%04d=%04d\n",MAX,MIN,n);
  32.        if(n==0||n==6174)break;
  33.     }
  34.     return 0;
  35. }

  1. #include <cstdio>
  2. #include <cmath>
  3.  
  4. int main() {
  5.     int a, b, c;
  6.     scanf("%d%d%d", &a, &b, &c);
  7.     int delta = b * b - 4 * a * c;
  8.     if (delta < 0) {
  9.         printf("No Solution");
  10.     } else if (delta == 0) {
  11.         printf("%.2f", -b / (2.0 * a));
  12.     } else {
  13.         printf("%.2f %.2f",  (-b - sqrt((double)delta)) / (2.0 * a), (-b + sqrt((double)delta)) / (2.0 * a));
  14.     }
  15.     return 0;
  16. }

5.2最大公约数与最小公倍数

  1. #include <cstdio>
  2. #include <cmath>
  3. int gcd(int a,int b){
  4.     if(b==0)return a;//求最大公约数的辗转相除法递归写法
  5.     else return gcd(b,a%b);
  6. }
  7. int main() {
  8.     int m,n;
  9.     while(scanf("%d%d",&m,&n)!=EOF){
  10.         printf("%d\n",gcd(m,n));
  11.     }
  12.     return 0;
  13. }

  1. #include <cstdio>
  2.  
  3. int gcd(int a, int b) {
  4.     if (b == 0) {
  5.         return a;
  6.     } else {
  7.         return gcd(b, a % b);
  8.     }
  9. }
  10.  
  11. int main() {
  12.     int a, b;
  13.     scanf("%d%d", &a, &b);
  14.     printf("%d", a / gcd(a, b) * b);
  15.     return 0;
  16. }

5.3分数的四则运算

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. struct Fraction {
  6.     int up, down;
  7. };
  8.  
  9. int gcd(int a, int b) {
  10.     if (b == 0) {
  11.         return a;
  12.     } else {
  13.         return gcd(b, a % b);
  14.     }
  15. }
  16.  
  17. Fraction reduction(Fraction fraction) {
  18.     if (fraction.down < 0) {
  19.         fraction.up = -fraction.up;
  20.         fraction.down = -fraction.down;
  21.     }
  22.     if (fraction.up == 0) {
  23.         fraction.down = 1;
  24.     } else {
  25.         int d = gcd(abs(fraction.up), abs(fraction.down));
  26.         fraction.up /= d;
  27.         fraction.down /= d;
  28.     }
  29.     return fraction;
  30. }
  31.  
  32. int main() {
  33.     Fraction fraction;
  34.     scanf("%d%d", &fraction.up, &fraction.down);
  35.     Fraction result = reduction(fraction);
  36.     if (result.down == 1) {
  37.         printf("%d", result.up);
  38.     } else {
  39.         printf("%d %d", result.up, result.down);
  40.     }
  41.     return 0;
  42. }

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. struct Fraction {
  6.     int up, down;
  7. };
  8.  
  9. int gcd(int a, int b) {
  10.     if (b == 0) {
  11.         return a;
  12.     } else {
  13.         return gcd(b, a % b);
  14.     }
  15. }
  16.  
  17. Fraction reduction(Fraction fraction) {
  18.     if (fraction.down < 0) {
  19.         fraction.up = -fraction.up;
  20.         fraction.down = -fraction.down;
  21.     }
  22.     if (fraction.up == 0) {
  23.         fraction.down = 1;
  24.     } else {
  25.         int d = gcd(abs(fraction.up), abs(fraction.down));
  26.         fraction.up /= d;
  27.         fraction.down /= d;
  28.     }
  29.     return fraction;
  30. }
  31.  
  32. Fraction add(Fraction f1, Fraction f2) {
  33.     Fraction result;
  34.     result.up = f1.up * f2.down + f2.up * f1.down;
  35.     result.down = f1.down * f2.down;
  36.     return reduction(result);
  37. }
  38.  
  39. int main() {
  40.     Fraction f1, f2;
  41.     scanf("%d%d%d%d", &f1.up, &f1.down, &f2.up, &f2.down);
  42.     Fraction result = add(f1, f2);
  43.     if (result.down == 1) {
  44.         printf("%d", result.up);
  45.     } else {
  46.         printf("%d %d", result.up, result.down);
  47.     }
  48.     return 0;
  49. }

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. struct Fraction {
  6.     int up, down;
  7. };
  8.  
  9. int gcd(int a, int b) {
  10.     if (b == 0) {
  11.         return a;
  12.     } else {
  13.         return gcd(b, a % b);
  14.     }
  15. }
  16.  
  17. Fraction reduction(Fraction fraction) {
  18.     if (fraction.down < 0) {
  19.         fraction.up = -fraction.up;
  20.         fraction.down = -fraction.down;
  21.     }
  22.     if (fraction.up == 0) {
  23.         fraction.down = 1;
  24.     } else {
  25.         int d = gcd(abs(fraction.up), abs(fraction.down));
  26.         fraction.up /= d;
  27.         fraction.down /= d;
  28.     }
  29.     return fraction;
  30. }
  31.  
  32. Fraction sub(Fraction f1, Fraction f2) {
  33.     Fraction result;
  34.     result.up = f1.up * f2.down - f2.up * f1.down;
  35.     result.down = f1.down * f2.down;
  36.     return reduction(result);
  37. }
  38.  
  39. int main() {
  40.     Fraction f1, f2;
  41.     scanf("%d%d%d%d", &f1.up, &f1.down, &f2.up, &f2.down);
  42.     Fraction result = sub(f1, f2);
  43.     if (result.down == 1) {
  44.         printf("%d", result.up);
  45.     } else {
  46.         printf("%d %d", result.up, result.down);
  47.     }
  48.     return 0;
  49. }

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. struct Fraction {
  6.     int up, down;
  7. };
  8.  
  9. int gcd(int a, int b) {
  10.     if (b == 0) {
  11.         return a;
  12.     } else {
  13.         return gcd(b, a % b);
  14.     }
  15. }
  16.  
  17. Fraction reduction(Fraction fraction) {
  18.     if (fraction.down < 0) {
  19.         fraction.up = -fraction.up;
  20.         fraction.down = -fraction.down;
  21.     }
  22.     if (fraction.up == 0) {
  23.         fraction.down = 1;
  24.     } else {
  25.         int d = gcd(abs(fraction.up), abs(fraction.down));
  26.         fraction.up /= d;
  27.         fraction.down /= d;
  28.     }
  29.     return fraction;
  30. }
  31.  
  32. Fraction multiply(Fraction f1, Fraction f2) {
  33.     Fraction result;
  34.     result.up = f1.up * f2.up;
  35.     result.down = f1.down * f2.down;
  36.     return reduction(result);
  37. }
  38.  
  39. int main() {
  40.     Fraction f1, f2;
  41.     scanf("%d%d%d%d", &f1.up, &f1.down, &f2.up, &f2.down);
  42.     Fraction result = multiply(f1, f2);
  43.     if (result.down == 1) {
  44.         printf("%d", result.up);
  45.     } else {
  46.         printf("%d %d", result.up, result.down);
  47.     }
  48.     return 0;
  49. }

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. struct Fraction {
  6.     int up, down;
  7. };
  8.  
  9. int gcd(int a, int b) {
  10.     if (b == 0) {
  11.         return a;
  12.     } else {
  13.         return gcd(b, a % b);
  14.     }
  15. }
  16.  
  17. Fraction reduction(Fraction fraction) {
  18.     if (fraction.down < 0) {
  19.         fraction.up = -fraction.up;
  20.         fraction.down = -fraction.down;
  21.     }
  22.     if (fraction.up == 0) {
  23.         fraction.down = 1;
  24.     } else {
  25.         int d = gcd(abs(fraction.up), abs(fraction.down));
  26.         fraction.up /= d;
  27.         fraction.down /= d;
  28.     }
  29.     return fraction;
  30. }
  31.  
  32. Fraction div(Fraction f1, Fraction f2) {
  33.     Fraction result;
  34.     result.up = f1.up * f2.down;
  35.     result.down = f1.down * f2.up;
  36.     return reduction(result);
  37. }
  38.  
  39. int main() {
  40.     Fraction f1, f2;
  41.     scanf("%d%d%d%d", &f1.up, &f1.down, &f2.up, &f2.down);
  42.     Fraction result = div(f1, f2);
  43.     if(!f2.up){
  44.     	printf("undefined");
  45. 	}
  46.     else if (result.down == 1) {
  47.         printf("%d", result.up);
  48.     } else {
  49.         printf("%d %d", result.up, result.down);
  50.     }
  51.     return 0;
  52. }

5.4素数 

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <cmath>
  4. using namespace std;
  5. bool isPrime(int n){
  6.     if(n<=1)return false;
  7.     int sqr=(int)sqrt(1.0*n);
  8.     for(int i=2;i<=sqr;i++){
  9.         if(n%i==0)return false;
  10.     }
  11.     return true;
  12.  
  13. }
  14. int main() {
  15.     int n;
  16.     scanf("%d",&n);
  17.     if(isPrime(n))printf("Yes");
  18.     else printf("No");
  19.     return 0;
  20. }

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <cmath>
  4. using namespace std;
  5. bool isPrime(int n){
  6.     if(n<=1)return false;
  7.     int sqr=(int)sqrt(1.0*n);
  8.     for(int i=2;i<=sqr;i++){
  9.         if(n%i==0)return false;
  10.     }
  11.     return true;
  12.  
  13. }
  14. int main() {
  15.     int n;
  16.     scanf("%d",&n);
  17.     for(int i=1;i<n+1;i++)
  18.     {
  19.         if(isPrime(i))printf("%d\n",i);
  20.  
  21.     }
  22.     return 0;
  23. }

5.5质因子分解

  1. #include <cstdio>
  2. int main() {
  3.     int n;
  4.     scanf("%d", &n);
  5.     int counter = 0;
  6.     while (n % 2 == 0) {
  7.         counter++;
  8.         n /= 2;
  9.     }
  10.     printf("%d", counter);
  11.     return 0;
  12. }

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <vector>
  5. using namespace std;
  6.  
  7. const int MAXN = 1000 + 1;
  8. bool isPrime[MAXN];
  9. vector<int> primes;
  10.  
  11. void getPrimes(int n) {
  12.     memset(isPrime, true, sizeof(isPrime));
  13.     for (int i = 2; i <= n; i++) {
  14.         if (isPrime[i]) {
  15.             primes.push_back(i);
  16.             for (int j = i + i; j <= n; j += i) {
  17.                 isPrime[j] = false;
  18.             }
  19.         }
  20.     }
  21. }
  22.  
  23. int main() {
  24.     int n;
  25.     scanf("%d", &n);
  26.     getPrimes((int)sqrt(1.0 * n));
  27.     for (int i = 0; i < primes.size() && n > 1; i++) {
  28.         int counter = 0;
  29.         while (n > 1 && n % primes[i] == 0) {
  30.             counter++;
  31.             n /= primes[i];
  32.         }
  33.         if (counter > 0) {
  34.             printf("%d %d\n", primes[i], counter);
  35.         }
  36.     }
  37.     if (n > 1) {
  38.         printf("%d 1", n);
  39.     }
  40.     return 0;
  41. }

5.6大整数运算 

  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. typedef vector<int> BigInt;
  8.  
  9. BigInt toBigInt(string nums) {
  10.     BigInt result;
  11.     for (int i = (int)nums.length() - 1; i >= 0; i--) {
  12.         result.push_back(nums[i] - '0');
  13.     }
  14.     return result;
  15. }
  16.  
  17. int compare(BigInt a, BigInt b) {
  18.     if (a.size() > b.size()) {
  19.         return 1;
  20.     } else if (a.size() < b.size()) {
  21.         return -1;
  22.     } else {
  23.         for (int i = (int)a.size() - 1; i >= 0; i--) {
  24.             if (a[i] > b[i]) {
  25.                 return 1;
  26.             } else if (a[i] < b[i]) {
  27.                 return -1;
  28.             }
  29.         }
  30.         return 0;
  31.     }
  32. }
  33.  
  34. int main() {
  35.     string nums1, nums2;
  36.     cin >> nums1 >> nums2;
  37.     BigInt a = toBigInt(nums1);
  38.     BigInt b = toBigInt(nums2);
  39.     int compareResult = compare(a, b);
  40.     if (compareResult < 0) {
  41.         printf("a < b");
  42.     } else if (compareResult > 0) {
  43.         printf("a > b");
  44.     } else {
  45.         printf("a = b");
  46.     }
  47. }

  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. typedef vector<int> BigInt;
  8.  
  9. BigInt toBigInt(string nums) {
  10.     BigInt result;
  11.     for (int i = (int)nums.length() - 1; i >= 0; i--) {
  12.         result.push_back(nums[i] - '0');
  13.     }
  14.     return result;
  15. }
  16.  
  17. BigInt add(BigInt a, BigInt b) {
  18.     BigInt c;
  19.     int carry = 0;
  20.     for (int i = 0; i < a.size() || i < b.size(); i++) {
  21.         int aDigit = i < a.size() ? a[i] : 0;
  22.         int bDigit = i < b.size() ? b[i] : 0;
  23.         int sum = aDigit + bDigit + carry;
  24.         c.push_back(sum % 10);
  25.         carry = sum / 10;
  26.     }
  27.     if (carry) {
  28.         c.push_back(carry);
  29.     }
  30.     return c;
  31. }
  32.  
  33. void print(BigInt a) {
  34.     for (int i = (int)a.size() - 1; i >= 0; i--) {
  35.         cout << a[i];
  36.     }
  37. }
  38.  
  39. int main() {
  40.     string nums1, nums2;
  41.     cin >> nums1 >> nums2;
  42.     BigInt a = toBigInt(nums1);
  43.     BigInt b = toBigInt(nums2);
  44.     print(add(a, b));
  45.     return 0;
  46. }

  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. typedef vector<int> BigInt;
  8.  
  9. BigInt toBigInt(string nums) {
  10.     BigInt result;
  11.     for (int i = (int)nums.length() - 1; i >= 0; i--) {
  12.         result.push_back(nums[i] - '0');
  13.     }
  14.     return result;
  15. }
  16. int compare(BigInt a, BigInt b) {
  17.     if (a.size() > b.size()) {
  18.         return 1;
  19.     } else if (a.size() < b.size()) {
  20.         return -1;
  21.     } else {
  22.         for (int i = (int)a.size() - 1; i >= 0; i--) {
  23.             if (a[i] > b[i]) {
  24.                 return 1;
  25.             } else if (a[i] < b[i]) {
  26.                 return -1;
  27.             }
  28.         }
  29.         return 0;
  30.     }
  31. }
  32. BigInt sub(BigInt a, BigInt b) {
  33.     BigInt c;
  34.     for (int i = 0; i < a.size() || i < b.size(); i++) {
  35.         int bDigit = i < b.size() ? b[i] : 0;
  36.         if (a[i] < bDigit) {
  37.             a[i + 1]--;
  38.             a[i] += 10;
  39.         }
  40.         c.push_back(a[i] - bDigit);
  41.     }
  42.      while (c.size() > 1 && c.back() == 0) {
  43.         c.pop_back();
  44.     }
  45.     return c;
  46. }
  47.  
  48. void print(BigInt a) {
  49.     for (int i = (int)a.size() - 1; i >= 0; i--) {
  50.         cout << a[i];
  51.     }
  52. }
  53.  
  54. int main() {
  55.     string nums1, nums2;
  56.     cin >> nums1 >> nums2;
  57.     BigInt a = toBigInt(nums1);
  58.     BigInt b = toBigInt(nums2);
  59.      if (compare(a, b) >= 0) {
  60.         print(sub(a, b));
  61.     } else {
  62.         cout << "-";
  63.         print(sub(b, a));
  64.     }
  65.     return 0;
  66. }

  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. typedef vector<int> BigInt;
  8.  
  9. BigInt toBigInt(string nums) {
  10.     BigInt result;
  11.     for (int i = (int)nums.length() - 1; i >= 0; i--) {
  12.         result.push_back(nums[i] - '0');
  13.     }
  14.     return result;
  15. }
  16. int compare(BigInt a, BigInt b) {
  17.     if (a.size() > b.size()) {
  18.         return 1;
  19.     } else if (a.size() < b.size()) {
  20.         return -1;
  21.     } else {
  22.         for (int i = (int)a.size() - 1; i >= 0; i--) {
  23.             if (a[i] > b[i]) {
  24.                 return 1;
  25.             } else if (a[i] < b[i]) {
  26.                 return -1;
  27.             }
  28.         }
  29.         return 0;
  30.     }
  31. }
  32. BigInt mul(BigInt a, int b) {
  33.     BigInt c;
  34.     int carry=0;;
  35.     for (int i = 0; i < a.size(); i++) {
  36.         int temp=a[i]*b+carry;
  37.         c.push_back(temp%10);
  38.         carry=temp/10;
  39.     }
  40.     while(carry!=0){
  41.         c.push_back(carry%10);
  42.         carry/=10;
  43.     }
  44.     while (c.size() > 1 && c.back() == 0) {
  45.         c.pop_back();
  46.     }
  47.     return c;
  48. }
  49.  
  50. void print(BigInt a) {
  51.     for (int i = (int)a.size() - 1; i >= 0; i--) {
  52.         cout << a[i];
  53.     }
  54. }
  55.  
  56. int main() {
  57.      string nums;
  58.     int b;
  59.     cin >> nums >> b;
  60.     BigInt a = toBigInt(nums);
  61.     print(mul(a, b));
  62.     return 0;
  63.     return 0;
  64. }

  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. typedef vector<int> BigInt;
  8.  
  9. BigInt toBigInt(string nums) {
  10.     BigInt result;
  11.     for (int i = (int)nums.length() - 1; i >= 0; i--) {
  12.         result.push_back(nums[i] - '0');
  13.     }
  14.     return result;
  15. }
  16.  
  17. BigInt mul(BigInt a, BigInt b) {
  18.     BigInt c = BigInt(a.size() + b.size() + 1, 0);
  19.     for (int i = 0; i < a.size(); i++) {
  20.         for (int j = 0; j < b.size(); j++) {
  21.             c[i + j] += a[i] * b[j];
  22.         }
  23.     }
  24.     for (int i = 0; i < a.size() + b.size(); i++) {
  25.         if (c[i] >= 10) {
  26.             c[i + 1] += c[i] / 10;
  27.             c[i] = c[i] % 10;
  28.         }
  29.     }
  30.     while (c.size() > 1 && c.back() == 0) {
  31.         c.pop_back();
  32.     }
  33.     return c;
  34. }
  35.  
  36. void print(BigInt a) {
  37.     for (int i = (int)a.size() - 1; i >= 0; i--) {
  38.         cout << a[i];
  39.     }
  40. }
  41.  
  42. int main() {
  43.     string nums1, nums2;
  44.     cin >> nums1 >> nums2;
  45.     BigInt a = toBigInt(nums1);
  46.     BigInt b = toBigInt(nums2);
  47.     print(mul(a, b));
  48.     return 0;
  49. }

  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. typedef vector<int> BigInt;
  8.  
  9. BigInt toBigInt(string nums) {
  10.     BigInt result;
  11.     for (int i = (int)nums.length() - 1; i >= 0; i--) {
  12.         result.push_back(nums[i] - '0');
  13.     }
  14.     return result;
  15. }
  16.  
  17. BigInt div(BigInt a, int b, int &r) {
  18.     BigInt c;
  19.     for (int i = (int)a.size() - 1; i >= 0; i--) {
  20.         r = r * 10 + a[i];
  21.         c.push_back(r / b);
  22.         r = r % b;
  23.     }
  24.     reverse(c.begin(), c.end());
  25.     while (c.size() > 1 && c.back() == 0) {
  26.         c.pop_back();
  27.     }
  28.     return c;
  29. }
  30.  
  31. void print(BigInt a) {
  32.     for (int i = (int)a.size() - 1; i >= 0; i--) {
  33.         cout << a[i];
  34.     }
  35. }
  36.  
  37. int main() {
  38.     string nums;
  39.     int b, r = 0;
  40.     cin >> nums >> b;
  41.     if (b == 0) {
  42.         cout << "undefined";
  43.         return 0;
  44.     }
  45.     BigInt a = toBigInt(nums);
  46.     BigInt q = div(a, b, r);
  47.     print(q);
  48.     cout << " " << r;
  49.     return 0;
  50. }

5.7扩展欧几里得算法

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. int gcd(int a, int b) {
  6.     if (b == 0) {
  7.         return a;
  8.     } else {
  9.         return gcd(b, a % b);
  10.     }
  11. }
  12.  
  13. int main() {
  14.     int a, b, c;
  15.     scanf("%d%d%d", &a, &b, &c);
  16.     printf(c % gcd(a, b) == 0 ? "Yes" : "No");
  17.     return 0;
  18. }

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. int exGcd(int a, int b, int &x, int &y) {
  6.     if (b == 0) {
  7.         x = 1;
  8.         y = 0;
  9.         return a;
  10.     }
  11.     int d = exGcd(b, a % b, x, y);
  12.     int temp = x;
  13.     x = y;
  14.     y = temp - a / b * y;
  15.     return d;
  16. }
  17.  
  18. int main() {
  19.     int a, b, x, y;
  20.     scanf("%d%d", &a, &b);
  21.     int d = exGcd(a, b, x, y);
  22.     int step = b / d;
  23.     int minX = (x % step + step) % step;
  24.     printf("%d %d", minX, (d - a * minX) / b);
  25.     return 0;
  26. }

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. int exGcd(int a, int b, int &x, int &y) {
  6.     if (b == 0) {
  7.         x = 1;
  8.         y = 0;
  9.         return a;
  10.     }
  11.     int d = exGcd(b, a % b, x, y);
  12.     int temp = x;
  13.     x = y;
  14.     y = temp - a / b * y;
  15.     return d;
  16. }
  17.  
  18. int solve(int a, int b, int c) {
  19.     int x, y;
  20.     int d = exGcd(a, b, x, y);
  21.     if (c % d) {
  22.         return -1;
  23.     } else {
  24.         int step = abs(b / d);
  25.         int minX = (c * x / d % step + step) % step;
  26.         return minX;
  27.     }
  28. }
  29.  
  30. int main() {
  31.     int a, b, c;
  32.     scanf("%d%d%d", &a, &b, &c);
  33.     int minX = solve(a, b, c);
  34.     if (minX == -1) {
  35.         printf("No Solution");
  36.     } else {
  37.         printf("%d %d", minX, (c - a * minX) / b);
  38.     }
  39.     return 0;
  40. }

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. int exGcd(int a, int b, int &x, int &y) {
  6.     if (b == 0) {
  7.         x = 1;
  8.         y = 0;
  9.         return a;
  10.     }
  11.     int d = exGcd(b, a % b, x, y);
  12.     int temp = x;
  13.     x = y;
  14.     y = temp - a / b * y;
  15.     return d;
  16. }
  17.  
  18. int solve(int a, int b, int c) {
  19.     int x, y;
  20.     int d = exGcd(a, b, x, y);
  21.     if (c % d) {
  22.         return -1;
  23.     } else {
  24.         int step = abs(b / d);
  25.         int minX = (c * x / d % step + step) % step;
  26.         return minX;
  27.     }
  28. }
  29.  
  30. int main() {
  31.     int a, c, m, x, y;
  32.     scanf("%d%d%d", &a, &c, &m);
  33.     int minX = solve(a, m, c);
  34.     if (minX == -1) {
  35.         printf("No Solution");
  36.     } else {
  37.         printf("%d", minX);
  38.     }
  39.     return 0;
  40. }

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. int exGcd(int a, int b, int &x, int &y) {
  6.     if (b == 0) {
  7.         x = 1;
  8.         y = 0;
  9.         return a;
  10.     }
  11.     int d = exGcd(b, a % b, x, y);
  12.     int temp = x;
  13.     x = y;
  14.     y = temp - a / b * y;
  15.     return d;
  16. }
  17.  
  18. int invert(int a, int m) {
  19.     int x, y;
  20.     int d = exGcd(a, m, x, y);
  21.     if (d != 1) {
  22.         return -1;
  23.     } else {
  24.         return (x % m + m) % m;
  25.     }
  26. }
  27.  
  28. int main() {
  29.     int a, m;
  30.     scanf("%d%d", &a, &m);
  31.     int result = invert(a, m);
  32.     if (result == -1) {
  33.         printf("No Solution");
  34.     } else {
  35.         printf("%d", result);
  36.     }
  37.     return 0;
  38. }

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. int exGcd(int a, int b, int &x, int &y) {
  6.     if (b == 0) {
  7.         x = 1;
  8.         y = 0;
  9.         return a;
  10.     }
  11.     int d = exGcd(b, a % b, x, y);
  12.     int temp = x;
  13.     x = y;
  14.     y = temp - a / b * y;
  15.     return d;
  16. }
  17.  
  18. int invert(int a, int m) {
  19.     int x, y;
  20.     int d = exGcd(a, m, x, y);
  21.     if (d != 1) {
  22.         return -1;
  23.     } else {
  24.         return (x % m + m) % m;
  25.     }
  26. }
  27.  
  28. int main() {
  29.     int n, a, m, b;
  30.     scanf("%d%d%d", &n, &a, &m);
  31.     int result = invert(abs(a), m);
  32.     for (int i = 0; i < n; i++) {
  33.         scanf("%d", &b);
  34.         result = (result * b) % m;
  35.     }
  36.     printf("%d", result);
  37.     return 0;
  38. }

5.8组合数

  1. #include <cstdio>
  2. int cal(int n,int p)
  3. {
  4.     if(n<p)return 0;
  5.     return n/p+cal(n/p,p);
  6.  
  7. }
  8. int main() {
  9.     int n,p=2;
  10.     scanf("%d", &n);
  11.     printf("%d", cal(n,p));
  12.     return 0;
  13. }

  1. #include <cstdio>
  2.  
  3. typedef long long LL;
  4.  
  5. LL C(LL n, LL m) {
  6.     LL ans = 1;
  7.     for (LL i = 1; i <= m; i++) {
  8.         ans = ans * (n - m + i) / i;
  9.     }
  10.     return ans;
  11. }
  12.  
  13. int main() {
  14.     LL n, m;
  15.     scanf("%lld%lld", &n, &m);
  16.     printf("%lld", C(n, m));
  17.     return 0;
  18. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小舞很执着/article/detail/817527
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号