UVA 11490 – Just Another Problem(数论)

全栈程序员站长

发布于 2022-07-07 16:45:39

1160

发布于 2022-07-07 16:45:39

文章被收录于专栏：全栈程序员必看全栈程序员必看

大家好，又见面了，我是全栈君。

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 <stdio.h>#include <string.h>#include <math.h>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;}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/116584.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年1月1，如有侵权请联系 cloudcommunity@tencent.com 删除

https