题意
求最小的因子个数大于\(500\)的三角形数
分析
可以发现三角形数\(\frac{n(n+1)}{2}\)?中的\(n\)?和\(n+1\)?是互质的。不妨设\(n\)?为偶数，那么\(d(\frac{n(n+1)}{2})=d(\frac{n}{2})d(n+1)\)??。
又有\(d(\frac{9699690}{2})\times d(9699689)=128\times8=1024\)?（其中\(9699690=2\times3\times5\times7\times11\times13\times17\times19\)???），只要用线性筛筛\({10}^7\)以内的质数即可。
代码
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int N(1e7);
int p[N],pcnt;
int c[N],cp[N],d[N];
int main() {
for(int i=2;i<N;i++) {
if(!p[i]) {
p[++pcnt]=i;
c[i]=1;
cp[i]=i;
d[i]=2;
}
for(int j=1;j<=pcnt && p[j]<N/i;j++) {
p[i*p[j]]=1;
if(i%p[j]!=0) {
c[i*p[j]]=1;
cp[i*p[j]]=p[j];
d[i*p[j]]=d[i]*2;
} else {
c[i*p[j]]=c[i]+1;
cp[i*p[j]]=cp[i]*p[j];
d[i*p[j]]=d[i/cp[i]]*(c[i*p[j]]+1);
break;
}
}
int x=i,y=i-1;
if(x%2) swap(x,y);
int ans=d[x]/(c[x]+1)*c[x]*d[y];
if(ans>500) {
cout<<i-1<<‘,‘<<i<<endl;
cout<<(1ll*x*y/2)<<endl;
break;
}
}
return 0;
}