uva 11490 ——Just Another Problem-蒲公英云

uva 11490 ——Just Another Problem

青旅半醒 2022-08-09 13:48 122阅读 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");
    }
}