#4051. 買不到的數目

題目來源：

//www.51cpc.com/problem/4051

小明開了一家糖果店。他別出心裁：把水果糖包成4顆一包和7顆一包的兩種。糖果不能拆包賣。小朋友來買糖的時候，他就用這兩種包裝來組合。當然有些糖果數目是無法組合出來的，比如要買 10 顆糖。你可以用電腦測試一下，在這種包裝情況下，最大不能買到的數量是17。大於17的任何數字都可以用4和7組合出來。本題的要求就是在已知兩個包裝的數量時，求最大不能組合出的數字。

輸入兩個正整數

輸出不能最大組合的數字

Sample input

4 7

Sample Output

像要你求最大，最小之類的題目大多數都是有技巧而言的，例如我們以後會碰到的貪心、動態規劃、數論等思想。所以說我們要用數學的思維去找出最簡單的方法。

要是硬解的話網上也有一大堆題解和對於數論公式的證明，那我重新寫一遍也沒什麼意義了。

我是初學者，數論什麼什麼的都不知道，我只是隱隱約約的感覺到這個應該和什麼公式有關。

然後我就用找規律的方法把它寫出來了。

首先，先暴力一小部分，輸出所有結果，

當然，寫的時候也不是那麼順利，因為存在無解的情況存在，所以陷入了無限循環，然後我將將那些肯定不存在的情況排除了。

然後就出現了

我們要尋找的是ans=f(n,m)，這樣的函數；

通過不斷試驗發現：ans= n * m – n – m;

那麼我們直接輸出公式就好了。

#include <stdio.h>

bool find(int m, int p, int q) {
    for(int i=0;i<1000;i++)
        for (int j = 0;j<1000;j++) 
            if (p * i + j * q == m) return true;
    return false;
}

int main()
{

    printf("n\tm\tans\n");
    for (int i = 2;i <= 20;i++)
        for (int j = 2;j <= 20;j++)
            for (int k = 1000;k >= 0;k--)
                if (!find(k, i, j)) {
                    if (k >= 999) break;
        //模擬的時候發現那些無解的數都符合這個條件，所以就用這個將其排除掉。
                    printf("%d\t%d\t%d\n", i, j, k);
                    break;
                }

    return 0;
}

尋找規律的程式碼。

#include <stdio.h>
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    printf("%d\n", n * m - n - m);
    return 0;
}

提交答案的程式碼

如果您覺得不錯就點個推薦或者收藏吧！

此題為分支，其根為：//www.cnblogs.com/Attacking-vincent/p/12721609.html

Tags: 【鞭長駕遠】從入門到喜愛