UVA - 11490 Just Another Problem （因数分解）

本文主要是介绍UVA - 11490 Just Another Problem （因数分解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

There is a wise saying “Nothingis unfair in love and war”. Probably that is why emperors of ancient days usedto use many funny and clever tricks to fool the opponents. The most commontechnique was to scare the opponent away by out numbering them with imaginarysoldiers. One of the funnier tricks (though hard to believe) was to give theown soldiers (not the opponent soldiers!) mild laxative dose so that there is along queue of soldiers in front of toilet. Seeing this queue from a distancethe opponent would miscalculate the total number of soldiers and flee away.This was a famous trick given by famous clown of the sub-continent named Gopal(The infamous “Gopal Bhar” to be precise). Another most common trick was tohave square shaped holes while arranging the soldiers in rows and columns. Suchan arrangement is shown below with 96 soldiers.

 

 

The strict property of sucharrangement for this problem is as follows:

 

(a)    The soldiershave to be arranged in rows and columns.

(b)   The border of thearrangement has to be rectangular.

(c)    The arrangementshould have soldiers missing only from the inner layers.

(d)   The soldiers should bemissing only from two equal square shaped regions. So the number of missingsoldiers should be twice of a strictly positive square number. In the figureabove the number of missing soldier is 2*2².

(e)    The thickness ofsoldiers should be equal every where (except the corners) in horizontal andvertical directions along the missing square. For example in the figure abovethe thickness of soldiers in horizontal and vertical directions along themissing square is always three. 

 

Now given the total number ofsoldiers S your job is to determine whether or not they can be arrangedaccording to the above mentioned rules.

 

Input

The input file contains 1000lines of inputs. Each line contains a positive integer S (S<1000000000000),where S is the total number of soldiers.

 

Input is terminated by linecontaining a single zero.

 

Output

For each line of input produceone or more line of output. Each line reports one possible number of possiblemissing soldiers which would enable the desired arrange with the S soldiers. Asthe number of possible missing soldiers can be quite large so instead of theactual number, the modulo 100000007 value should be printed. Also if there ismore than one possible value for number of missing soldiers the modulo100000007 values should be reported in descending order of the original numberof soldier (Not the modulo value). If no such number of missing soldiers isfound print the line “No Solution Possible” instead.

 

Print a blank line after theoutput for each line of input. Look at the output for sample input for details.

 

Sample Input                              Output for Sample Input

96 102 11100 0

Possible Missing Soldiers = 8   No Solution Possible   Possible Missing Soldiers = 553352 Possible Missing Soldiers = 308898 Possible Missing Soldiers = 45000 Possible Missing Soldiers = 3528

Problem Setter: ShahriarManzoor

Special Thanks: Syed MonowarHossain.

题意：你有S个士兵，并打算把他们排成一个r行c列的矩阵，但是可以有两个”洞“的矩形方队，方队的边界必须是都有人站，且每个洞的4个方向的”厚度“都是一样的，求可能缺失的人数

思路：设厚度为a，那么可以得到：(3a+2c)*(2a+c) = S + 2*c^2, 推出 6a^2+7ac = S,然后就是枚举a了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
typedef long long ll;
using namespace std;
const ll mod = 100000007;ll n;int main() {while (scanf("%lld", &n) != EOF && n) {ll m = sqrt(n/6+0.5);	int flag = 0;for (ll i = 1; i <= m; i++) {if ((n-6*i*i) % (7*i) == 0) {ll cur = (n-6*i*i) / (7*i);if (cur <= 0)continue;cur %= mod;flag = 1;printf("Possible Missing Soldiers = %lld\n", (2*(cur*cur%mod))%mod);}	}if (!flag)printf("No Solution Possible\n");printf("\n");}return 0;
}

这篇关于UVA - 11490 Just Another Problem （因数分解）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---