11490 - Just Another Problem

题目链接

题意：有S个士兵，排成一个矩阵，矩阵中可以有两个洞，要求两个洞上下左右厚度一样，问能缺少士兵的情况数。

思路：推推公式，设厚度为a, 正方形为i, 那么(3 a + 2 i) (2 a + i) = S + 2 i i;
化简一下得到6 i i + 7 a i = S
由于S很大，所以去枚举厚度，这样只要枚举到sqrt(S)就够了，复杂度可以接受

代码：

#include 
  
   
#include 
   
     #include 
    
      const long long MOD =100000007; long long n; int main() { while (~scanf("%lld", &n) && n) { int flag = 1; for (long long i = 1; i * i * 6 < n; i++) { long long tmp = n - i * i * 6; if (tmp % (7 * i) == 0) { long long ans = tmp / (7 * i) % MOD; printf("Possible Missing Soldiers = %lld\n", ans * ans * 2 % MOD); flag = 0; } } if (flag) printf("No Solution Possible\n"); printf("\n"); } return 0; }