题解：P10390 [蓝桥杯 2024 省 A] 因数计数

思路 （是 @Iceturky 的思路，在此拜谢） 值域小，为了方便表示设值域 。先开桶 表示 出现的次数。同时预处理出每个数编号不相等的因数个数 和倍数个数 ，时间复杂度为调和级数 。 考虑先算出 且 的 数量 ，枚举较小数 ，得 。 有了以上问题的答案，平方一下就是 且 的 组数，还需要容斥减去 的组数。 首先先减去满足一个条件的： • ，较小数相等，枚举这个数 ，取两个倍数，组数为 。 • ，较大数相等，枚举这个数 ，取两个因数，组数为 。 • 或 ，即一组中较大数与另一组中较小数相等。枚举相等的中间值 ，取一个因数和一个倍数，组数为 。 还需要加上满足两个条件的： • 且 ，此时两个较小数和两个较大数分别相等，组数即为最初求出的 数量 。 • 且 ，由于倍数的要求限制了 ，所以此时 均相等，枚举相等值 ，组数为 。 • 其他四种情况都会产生 或 ，与已经确定的条件 冲突，所以组数为 。 之后满足三个或四个条件也会产生同样的冲突，组数均为 ，不用处理。 这样就做完了，但是由于 达到了 级别，开 __int128 才能确保通过。 代码 #include #define int __int128 using namespace std; const int N=1e5+10; const int P=1e5; int read() { int s=0,w=1; char ch; ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-') w=-1; ch=getchar();} while(ch>='0'&&ch<='9') s=s10+ch-'0',ch=getchar(); return sw; } void print(int x) { if(x>=10) print(x/10); putchar(x%10+'0'); } int n,ans,t[N],s[N],b[N]; signed main() { n =read(); for(int i=1;i<=n;i++) t[read()]++; for(int i=1;i<=P;i++) if(t[i]) { for(int j=i*2;j<=P;j+=i) if(t[j]) b [i]+=t[j],s[j]+=t[i]; b [i]+=t[i]-1,s[i]+=t[i]-1; ans +=t[i]*b[i]; } ans *=(ans+1); //无限制和 i=k && j=l for(int i=1;i<=P;i++) if(t[i]) { ans -=t[i]*b[i]*b[i]; // i=j ans -=t[i]*s[i]s[i]; // k=l ans -=2t[i]*b[i]s[i]; // i=l || j=k ans +=t[i](t[i]-1); // i=l && j=k } print(ans); return 0; }