Project Euler 276 Primitive Triangles

Posted on | 阅读数 次
Words count in article: 408 | Reading time ≈ 1

开启传送门

题目描述

Consider the triangles with integer sides $a, b$ and $c$ with $a \leq b \leq c$.
An integer sided triangle $(a,b,c)$ is called primitive if $gcd(a,b,c)=1$.
How many primitive integer sided triangles exist with a perimeter not exceeding $10,000,000$?

题意

问你存在多少个边长是整数的三角形,并且满足三边长的gcd为1,周长不超过$1e7$.

分析

有一个比较奇奇怪怪的结论

我直接把结论搬过来$\dots$

\begin{eqnarray}
F(n) =
\begin{cases}
\lfloor\frac{(n+3)^2+24}{48}\rfloor\ \ \ \ &n\ \ is\ \ odd\\
\lfloor\frac{n^2+24}{48}\rfloor\ \ \ \ &n\ \ is\ \ even\
\end{cases}
\end{eqnarray}

这个结论说的是,周长为$n$的边长都是整数的三角形的数量.然后我们可以预处理出所有的周长为$n$的数量出来,然后我们怎么保证gcd呢,比较好想的就是容斥,我们容斥掉所有gcd不是1的就行了,也就是说我们用周长为$2\cdot n,3\cdot n,\dots$的减去周长为$n$的就行啦啦啦

给大佬递上我奇丑无比的代码　(/ω＼)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
const int maxm = 1e7+1;
long long num[maxm];
long long get(long long a){
	if(a&1) return ((a+3)*(a+3)+24)/48;
	return (a*a+24)/48;
}
void init(){//预处理出每个周长对应的三角形数量,容斥得到正确的数量
	for(int i = 1;i<maxm;i++) num[i] = get(i);
	for(int i = 1;i<maxm;i++) for(int j = i<<1;j<maxm;j+=i) num[j]-=num[i];
}
int main(){
	init();
	long long ans = 0;
	for(int i = 1;i<maxm;i++) ans+=num[i];
	cout<<ans<<endl;
	return 0;
}