poj2429 GCD & LCM Inverse 数论 质因数分解

题意:输入两个数分别为 c , d 找到最小的 a + b 使得 Gcd(a,b) = c ; Lcm(a,b) = d; 找到 这样 的 a 与 b ,使得 a+b最小,而且要让 a=1;fac--){ if(C % fac ==0) { ans1 = fac;break; } } for(ll fac = mid;fac >=1,x); if(t!=1&&t!=x-1) return false; if(t==x-1) return true;// t =x -1 而不是1的情况下 不能继续套用二次探索 // 因为 x ^2 ≡1 是二次探索的右边 这时候右边是 x - 1 不能继续用了 认为通过测试. } return true; } bool Miller_Rabin(ll x){ for(int i=0;i=0 ? x : (-x) ; } ll dfs(ll n){ ll x1 = 0 , x2 =0, c= rand()%(n-1) + 1; ll val = 1; for(ll i=1;;i