优化的程序用于通过= C与positve整数解决斧+

我被= c其中x和y写一个程序，对于任何给定的正整数a < b <Ç将输出YES，如果有一个解决方案，AX +也是正整数（x，y> 0），否则如果没有解。请记住，我需要使用大数字。优化的程序用于通过= C与positve整数解决斧+

我解决这个问题的方法是，我从c中减去b，然后检查这个数是否可以被a分解。

这里是我的代码：

#include <stdio.h> 
#include <stdlib.h> 

int main(){ 
    unsigned long long int a, b, c; 
    scanf("%I64u %I64u %I64u", &a, &b, &c); 
    while(c>=a+b){ //if c becomes less than a+b, than there's no sollution 
     c-=b; 
     if(c%a==0){ 
      printf("YES"); 
      return 0; 
     } 
    } 
    printf("NO"); 
    return 0; 
}

有通过= C找到阉AX +更优化的方式有积极sollutions？我尝试阅读线性丢番图方程，但是我找到的所有方法都是找到整数解（但不是正数）的方法。

来源

2014-12-20 David Simka

是否每个单个变量都被限制为仅限整数？ – shuttle87

@ shuttle87是的，a，b和c是正整数，所以如果它们存在的话应该是x和y。 –

你不应该太多地保存你的空格，代码看起来很丑并且可读性较差。 – dtech

以下是评论，但评论部分太大了。

本文旨在帮助他人深入研究这个问题。

OP：如果你喜欢，可以在你的文章中加入任何内容。

仍然需要的是一些具有挑战性的a,b,c。

#include <limits.h> 
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

//#define LLF "%I64u" 
#define LLF "%llu" 

int main(void) { 
    unsigned long long int a, b, c, x, y, sum, c0; 
    // scanf(LLF LLF LLF, &a, &b, &c); 
    c = c0 = ULLONG_MAX; 
    b = 10000223; 
    a = 10000169; 
    y = 0; 
    sum = a + b; 
    time_t t0 = time(NULL); 
    while (c >= sum) { //if c becomes less than a+b, than there's no solution 
    c -= b; 
    if (c % a == 0) { 
     break; 
    } 
    } 
    if (c % a == 0) { 
    y = (c0 - c)/b; 
    x = c/a; 
    printf("YES " LLF "*" LLF " + " LLF "*" LLF " = " LLF "\n", a, x, b, y, c); 
    } else { 
    printf("NO\n"); 
    } 
    time_t t1 = time(NULL); 
    printf("time :" LLF "\n", (unsigned long long) (t1 - t0)); 
    return 0; 
}

输出

YES 10000169*1844638544065 + 10000223*4688810 = 18446697184563946985 
time :0

来源

2014-12-21 01:33:06 chux

我的方法为止。

使用Euclidean Algorithm找GCD（A，B）
有解决方案（以整数），以AX + = C当且仅当GCD（A，B）把温度。没有整数解决方案意味着没有正解
使用Extended Euclidean Algorithm来解决Diophantine equation，如果给出非正解，则返回NO。

对于比较很难发现，需要比第二，但在决定成千上万随机方程的性能差异是显着较长的例子。 This Lecture有一个求解线性不定方程的正解的数目的解。

typedef unsigned long long int BigInt; 
int pos_solvable(BigInt a, BigInt b, BigInt c) { 
    /* returns 1 if there exists x, y > 0 s.t. ax + by = c 
    * where 0 < a < b < c 
    * returns 0, otherwise 
    */ 
    BigInt gcd = a, bb = b, temp; 
    while (bb) { /* Euclidean Algorithm */ 
    temp = bb; 
    bb = gcd % bb; 
    gcd = temp; 
    } 
    if (c % gcd) { /* no integer (or positive) solution */ 
    return 0; 
    } else { 
    /* Extended Euclidean Algorithm */ 
    BigInt s = 0, old_s = 1; 
    BigInt t = 1, old_t = 0; 
    BigInt r = b/gcd, old_r = a/gcd; 

    while (r > 0) { 
     BigInt quotient = old_r/r; 
     BigInt ds = quotient * s; 
     BigInt dt = quotient * t; 
     if (ds > old_s || dt > old_t) 
     return 0; /* will give non-positive solution */ 

     temp = s; 
     s = old_s - ds; 
     old_s = temp; 

     temp = t; 
     t = old_t - dt; 
     old_t = temp; 

     temp = r; 
     r = old_r - quotient * r; 
     old_r = temp; 
    } 
    return 1; 
    } 
}

来源

2014-12-21 05:14:17 ryanpattison

优化的程序用于通过= C与positve整数解决斧+

回答

相关问题