[CSP-S模拟测试]:木板（数学）

题目传送门（内部题68）

输入格式

输入有若干行，每行一个整数$N$，以$0$结束

输出格式

每行一个整数表示方案数，方案不同当且仅当$E$、$F$、$G$的坐标不同

样例

样例输入：

10
20
100
32
0

样例输出：

0
8
72
24

数据范围与提示

对于$40\%$的数据，$N\leqslant 10^7$
对于另外$10\%$的数据，$N$是质数
对于$100\%$的数据，$N\leqslant 10^{14}$不超过$5$组数据

题解

一个正方形有四个角，一个角有两种情况，不妨我们只算一个角的一种情况，最后再乘$8$。

为方便，先做如下定义：

初中老师告诉我们，$\bigtriangleup BCE\backsim \bigtriangleup EDF$，所以有$\dfrac{n}{a}=\dfrac{b}{c}$。

$\therefore nc=ab$。

又$\because a+b=n$。

$\therefore nc=a(n-a)$。

把$n$除过去可以得到$\dfrac{a(n-a)}{n}=c$。

再化简就可以得到$a-\dfrac{a^2}{n}=c$。

那么要求$n|a^2$，于是可以将$n$分解质因数，那么最小的$a$至少要有$n$中每个质因子个数的一半（上取整）。

其他可行解就是$a$的整数倍。

时间复杂度：$\Theta(T\sqrt{n})$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>
using namespace std;
long long n;
long long ans;
int main()
{
	while(1)
	{
		scanf("%lld",&n);
		if(!n)break;ans=0;
		for(long long i=1;i*i<=n;i++)
			if(!(n%(i*i)))ans=(i-1)*8;
		printf("%lld\n",ans);
	}
}

rp++

[CSP-S模拟测试]:木板（数学）

原文：https://www.cnblogs.com/wzc521/p/11663741.html