UVa

Luogu

Vjudge

分析

灰题+1

设周围士兵的「厚度」为 $x$ ，洞的边长为 $y$ 。

很容易列出如下方程

$$ (2x+y)(3x+2y)-2y^2=S $$

化简得到

$$ 6x^2+7xy=S $$

左边因式分解得到

$$ x(6x+7y)=S $$

于是枚举 $S$ 的约数 $x$ ，然后算出 $y$ 即可。注意要判断是否合法。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int mod=1e8+7;

int S;

signed main() {
    while (S=read()) {
        int flag=0;
        for (re int i=1;i*i<=S;++i) {
            if (S%i) continue;
            int x=i;
            if ((S/x-6*x)%7) continue;
            int y=(S/x-6*x)/7;
            if (y<=0||y>=S) continue;
            printf("Possible Missing Soldiers = %lld\n",2*y%mod*y%mod);
            flag=1;
        }
        if (!flag) puts("No Solution Possible");
        puts("");
    }
    return 0;
}