modで最大値を算出，高速化

Question

下記のリンクでの問題において5つくらいのケースでTLEが起きてしまうのですが，modでの最大値はどのようにすれば早く求めることが出来ますでしょうか．
whileの終了条件があまりよくないのだろうという考えには至るのですが，maxが二週目でも同じであるというやり方以外にどのようなものがありますか？
問題

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


int main(void){

    int numG,capacity;

    scanf("%d %d",&numG,&capacity);

    int ans=0;
    int sum_capa=0;

    if(numG%capacity==0){
        printf("0\n");
        return 0;
    }
    
    while(1){
        sum_capa+=capacity;
        if(sum_capa>=numG) break;
    }
    int part=sum_capa-numG;
    int max=0;
    int cal=0;
    while(1){
        cal+=part;
        cal%=capacity;
        if(max==cal) break;
        if(max<cal) max=cal;
        if(max==capacity-1) break;


    }
    printf("%d\n",max);
    return 0;
}

Answer 1

一次不定方程式の考え方を使うのが1番速いと思います。
xグループ参加し、それに対して必要なバスがy台としたときに、空席がr席(0≦r<M)とすると、
My-Nx=r (A)
という関係が成り立つことになります。
このrとして取りうる値のうち、最大の値を求めるのがこの問題の趣旨となります。

ある値がrとして取りうるか否かは、
方程式(A)を満たす整数x,y(整数解)が存在するか否か、と同義になります。
例えばN=6,M=4の場合、

• r=3、つまり4y-6x=3を満たす整数x,yは存在しません。(左辺は偶数、右辺は奇数のため)

つまり、「空席が3つ」という状況は起こりえません。

• r=2、つまり4y-6x=2は、x=1,y=2や、x=3,y=5などが解になります。

これらの状況で、「空席が2つ」になります。

x,yについての方程式(A)は、
rが「MとNの最大公約数」の倍数である場合に、またその場合に限り整数解をもつことが知られています。
→一次不定方程式ax+by=cの整数解 - 高校数学の美しい物語
(厳密には、この問題においてx,yは自然数である必要がありますが、
M>0,N>0であれば自然数解をもつことが保証されます。)

以下、「MとNの最大公約数」をgとします。
Mはgの倍数であるため、M = kgとなる自然数kが存在します。
(A)が整数解をもつためにrとして取りうる値は、
0≦r<Mの範囲内にあるgの倍数、すなわち
0, g, 2g, ... , (k-1)g
のk個であり、このうち最大は
(k-1)g = kg - g = M - g
となります。
つまり、求める空席の最大値はM - gで表せることになります。
gは、ユークリッドの互除法により高速に求められるので、総当たりのループより速く解決できます。

Comments

[kazuma-s]

N と M の最大公約数が M の時と、そうでない時とを場合分けしなくてもよいのではありませんか？
ということで、
int n, m, g, r;
scanf("%d%d", &n, &m);
for (g = m; r = n % g; g = r) n = g;
printf("%d\n", m - g);

[swordone]

整理し、例を挙げながらの回答に修正しました。

[grape_ll]

このように数学的な面から攻めるとうまくいくのですね．大変参考になりました．説明もとても分かりやすかったです．ありがとうございます．