uva 11490 ——Just Another Problem

青旅半醒 2022-08-09 13:48 38阅读 0赞

题意：刚开始并没有看懂，耐着性子硬读下去，才勉强弄懂大意，英语也要加强训练啊！  
题目是说你有s行c列士兵，然后带着他们去打仗，为了虚张声势，在士兵的中间缺了两个边长为r的洞，且这两个洞四个方向的厚度是一样的，理解可能不大好理解，但是画一下就明了了，题目中也有相关的图，这个应该能yy到，然而重点是要求的问题和这个刚好一反，要求的是给定n个人，问这个洞有多大（问可能会缺少多少人）

思路：设中间两个洞的边长为r，洞的四个方向的厚度为c  那么极易推出（2r+3c）\*（r+2c） --2r^2= n ，稍微化简可以得到 6c^2+7cr=n，即c（6c+7r)=n, c是n的约数，那么只要对n进行因式分解，对分解的因数一一枚举，那么就可以求出所有的可能性，没必要把因式分解后然后排序，没有必要，如果外加拉宾—米勒的素数判别，速度会更快！  
  
code：

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <string>
    using namespace std;
    
    typedef long long ll;
    const ll mod=100000007;
    
    int main()
    {
        
        ll n;
        while (~scanf ("%lld",&n)&&n)
        {
        
            int f=1;
            for (ll i=1;i<(ll)sqrt(1.0*n/6+0.5);i++)    //依次按顺序分解枚举因子
            {
        
                ll t=n-6*i*i;
                if (t%(7*i)==0)
                {
        
                    ll ans=t/(7*i)%mod;
                    ans=2*ans*ans%mod;
                    printf("Possible Missing Soldiers = %lld\n",ans);
                    f=0;
                }
            }
            if (f)
                printf("No Solution Possible\n");
            printf("\n");
        }
    }