关于若干质数的较好性质【裴蜀定理等】

1、若a与b互质，则a*b与a+b互质

2、【裴蜀定理】现在有整数方程：

ax + by + cz + ..... = t（a b c都是整数可正可负，t是整数可正可负）

有整数解的充要条件是：

gcd(a,b,c) | t（gcd是a、b、c......绝对值的最大公因数）

【注意：a b c......全为正数的题目比较常见】

3、（2的推论）

若a,b,c为正整数，则gcd(a,b,c...) == 1的充要条件是存在x,y,z......（整数），使得ax+by+cz+...... = 1有整数解.

 

P4549 【模板】裴蜀定理

使用的定理：定理2

AC代码：

#include<iostream> #include<stdio.h> using namespace std; int gcd(int x,int y){ return y == 0?x:gcd(y,x%y); } int main(){ int n; cin >> n; int t; scanf("%d",&t); int ans = t; for(int i = 2;i <= n;i++){ scanf("%d",&t); if(t < 0) t = -t; ans = gcd(ans,t); } printf("%d\n",ans); }

 

A Simple Math Problem

解读【转载】：一个简单的数学问题 题解

我的AC代码：

#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> using namespace std; int gcd(int x,int y){ return y == 0?x:gcd(y,x%y); } int main(){ int a,b; while(scanf("%d%d",&a,&b) != EOF){ int c = gcd(a,b); double dt = sqrt(a*a-4*b*c); if(int(dt) != dt){//如果delta开根号之后不是整数 printf("No Solution\n"); continue; } int fz1 = a+int(dt); //分子 int fz2 = a-int(dt); if(fz1/2*2 != fz1){ printf("No Solution\n"); continue; } else{ printf("%d %d\n",fz2/2,fz1/2); } } }