前言：

WTCL，居然折磨煎蛋的性质都忘记了，WTCL。

考场上想出来了正解，就差一点就能A掉，挺难受的。

要记住一个数n可能会有一个大于\(\sqrt{n}\)的质因子。。我忘记把它加进去了。。。。

解析：

相似三角形是很显然的。

最后式子变成\(\frac{i^2}{n},i\in[1,n-1]\) 。

求令这个式子是整数的i的个数。

显然把n分解质因数，因为上面是\(i^2\) 所以，假设n中有一个\(p^j\),那么i中至少要有\(p^{\lceil\frac{j}{2}\rceil}\).

然后。。只要把这些\(p_i^{\lceil\frac{j_i}{2}\rceil}\)都乘在一起，然后再用(n-1)除掉，就完了。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=10000000+10,ss=1e7+10;

ll n,ans;

bool is_not_prime[maxn];

int prime[maxn];

int cnt;

vector <int> tot,pr;

void Solve1(){

	int aa=0;

	for(register int i=1;i<n;++i){

		ll res=1ll*i*(n-i);

		if(res%n) continue;

		aa++;

	}

	printf("%d\n",aa*8);

}

ll qpow(int x,int y){

	ll base=x;

	ll res=1;

	while(y){

		if(y&1) res=res*base;

		base=base*base;

		y>>=1;

	}

	return res;

}

void Solve2(){

	pr.clear();

	tot.clear();

	ll xx=n;

	for(int i=1;i<=cnt;++i){

		if(n%prime[i]) continue;

		int tool=0;

		while(n%prime[i]==0){

			tool++;

			n/=prime[i];

		}

		pr.push_back(prime[i]);

		tot.push_back(tool);

	}

	ll aa=n;

	for(int i=0;i<pr.size();++i) aa*=qpow(pr[i],(tot[i]+1)>>1);

	ans=(xx-1)/aa;

	printf("%lld\n",ans*8);

}

void xxs(){

	is_not_prime[0]=is_not_prime[1]=1;

	for(int i=2;i<=10000000;++i){

		if(!is_not_prime[i]) prime[++cnt]=i;

		for(int j=1;j<=cnt&&i*prime[j]<=10000000;++j){

			is_not_prime[i*prime[j]]=1;

			if(i%prime[j]==0) break;

		}

	}

}

void Solve(){

	xxs();

	while(1){

		scanf("%lld",&n);

		if(n==0) return;

		if(n<=ss){

			Solve1();

			continue;

		}

		Solve2();

	}

}

int main(){

	//freopen("tri.in","r",stdin);

	//freopen("tri.out","w",stdout);

	Solve();

	return 0;

}

上午小测1 T1 木板 题解的相关教程结束。