2020.09.13組チームトレーニング問題C:Cocoa Coalition(数学)

問題C:Cocoa Coalition時間制限:1 Secメモリ制限:128 MB
タイトルはAlice and Bob decide to share a chocolate bar,which is an n by m rectangular grid of chocolate cells.They decide that Alice should get a < n·m pieces and that Bob should get b = n·m − a pieces. To split the chocolate bar, they repeatedly take a single piece of chocolate and break it either horizontally or vertically, creating two smaller pieces of chocolate. See Figure C.1 for an example. What is the minimum number of splits that Alice and Bob need to perform in order to split the n-by-m chocolate bar into two piles consisting of a and b chocolate cells?
Figure C.1: Illustration of a solution to Sample Input 2, showing the original 10-by-10 chocolate bar split three times into pieces of size 10-by-2, 10-by-5, 3-by-3 and 7-by-3. Giving Alice the 10-by-5 and 7-by-3 pieces, she gets a total of 50 + 21 = 71 chocolate cells. The input consists of a single line,containing the three integers n,m and a(1≦n,m≦106,1≦a ： , a 。
構想:最大3回切ることを発見した.普通は1回に2回か3回必要です.1回2回を除いたのは3回です.具体的な手順はコードを参照してください.

#include
using namespace std;
const int N=1e3+15;
typedef long long ll;
int main()
{
     
    ll n,m,a,b;
    cin>>n>>m>>a;
    if(n>m)
        swap(n,m);
    b=n*m-a;
    if(a%n==0||a%m==0)
    {
     
        cout<<"1"<<endl;    return 0;
    }
    for(int i=1;i<=sqrt(a);i++)
    {
     
        if(a%i==0)
        {
     
            ll l1=i,l2=a/i;
            if(l1>l2)
                swap(l1,l2);
            if(n>=l1&&m>=l2)
            {
     
                cout<<"2"<<endl;    return 0;
            }
        }
    }
    a=n*m-a;
    for(int i=1;i<=sqrt(a);i++)
    {
     
        if(a%i==0)
        {
     
            ll l1=i,l2=a/i;
            if(l1>l2)
                swap(l1,l2);
            if(n>=l1&&m>=l2)
            {
     
                cout<<"2"<<endl;    return 0;
            }
        }
    }
    cout<<"3"<<endl;
    return 0;
}