自动搬运

查看原文

来自洛谷，原作者为

	Elairin176 AFOed（2021.10.23 - 2025.4.12）

搬运于2025-08-24 22:45:09，当前版本为作者最后更新于2023-02-13 19:12:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

传送门
数学好题。
首先，题目要求 $b$ 是 $a$ 的倍数，$c$ 是 $b$ 的倍数，$a+b+c=n$，所以 $a$ 一定是 $n$ 的因数。
接下来我们推一下 $a,b,c$ 的值域。
$a$ 比较好想，最大的时候柿子为 $a+2a+4a=n$，即 $7a=n$，所以 $a\in[1,\lfloor\frac{n}{7}\rfloor]$。
$b$ 最小的时候只能是 $2a$，最大的时候需要考虑到 $c$。最大时柿子为 $a+b+2b=n$，这里容易发现 $b=\frac{n-a}{3}$，所以 $b\in[2a,\lfloor\frac{n-a}{3}\rfloor]$。
$c$ 最小的时候是 $2b$，最大时柿子为 $a+2a+c=n$，容易得出 $c=n-3a$，所以 $c\in[2b,n-3a]$。
所以，我们可以先把 $a$ 的因数找出来，之后枚举一下，超过 $\lfloor\frac{n}{7}\rfloor$ 就不枚举。
设这个因数为 $x$，那么 $a=x$，$b+c=n-x=ya+zya$。
$a+b+c=a+ya+zya=a\times(1+y+zy)$，设 $d=\frac{n}{a}-1$，这里的 $d=y+zy$。
我们需要求出满足条件的 $y,z$ 有多少组。
我们枚举 $y$，从 $2$ 开始，不能出现 $ay\le \lfloor\frac{n-a}{3}\rfloor$ 的情况。
容易发现，在 $(a-y)\bmod y=0$ 的情况下可以构造出一组解。这个柿子等同于 $a\bmod y=0$。
所以，这个问题转化成了求解 $a$ 的因数数量。
$y$ 只需要枚举到 $\sqrt{a}$ 就可以。
对于一个满足条件的 $y$，如何判断 $\frac{n}{y}$ 也满足情况呢？
首先，需要有 $\frac{n}{y}≠y$。
这里需要判断能否构造出 $c$，如果 $(a-\frac{a}{y})\bmod \frac{a}{y}≠0$，那么无法构造出 $c$，$y$ 就不对。
还需要判断 $a-\frac{a}{y}=\frac{a}{y}$。如果等于，说明 $b=c$，是错误的。
CODE：

//Code by __dest__ruct__or__(uid=592238)
#include <iostream>
#include <vector>
using namespace std;
#define umap unordered_map
#define uset unordered_set
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<long long,long long>
const ll INF=9223372036854775807;
namespace mySTL{
	inline int max(int a,int b){return a>b?a:b;}
	inline int min(int a,int b){return a<b?a:b;}
	inline ll max(ll a,ll b){return a>b?a:b;}
	inline ll min(ll a,ll b){return a<b?a:b;}
	inline ld min(ld a,ld b){return a<b?a:b;}
	inline ld max(ld a,ld b){return a>b?a:b;}
	inline int _abs(int a){return a<0?-a:a;}
	inline int read(){char c=getchar();int f=1,ans=0;
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9')ans*=10,ans+=c-'0',c=getchar();
	return ans*f;}
	inline long long readll(){char c=getchar();long long f=1,ans=0;
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9')ans*=10,ans+=c-'0',c=getchar();
	return ans*f;}
	inline void swap(int &a,int &b){a^=b,b^=a,a^=b;}
	inline void swap(ll &a,ll &b){a^=b,b^=a,a^=b;}
	inline void write(int x){if(x<0){putchar('-');x=-x;}
	if(x>=10){write(x/10);}putchar(x%10+'0');}
	inline void writell(long long x){if(x<0){putchar('-');x=-x;}
	if(x>=10){writell(x/10);}putchar(x%10+'0');}
	inline ll pw(ll a,ll b,ll p){if(b==0)return 1;
	if(b==1)return a%p;
	ll mid=pw(a,b/2,p)%p;
	if(b&1)return mid*mid%p*a%p;else{return mid*mid%p;}}
	inline int gcd(int a,int b){return b?gcd(b,a%b):a;}
	inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
	inline int lcm(int a,int b){return a*b/gcd(a,b);}
}
using namespace mySTL;
int n,ans,sz,a;
vector<int>v;
int main(void){
	n=read();
	for(int i=1;i<=n/i;i++){//求因数
		if(n%i!=0){
			continue;
		}
		v.push_back(i);
		if(i!=n/i){
			v.push_back(n/i);
		}
	}
	sz=v.size();
	for(int i=0;i<sz;i++){//枚举因数（构造a）
		if(v[i]>n/7){
			continue;
		}
		a=n/v[i]-1;
		for(int j=2;j*v[i]<=(n-v[i])/3&&j<=a/j;j++){//构造y
			if(a%j==0){
				ans++;
				if(a/j!=j&&(a-a/j)%(a/j)==0&&(a-a/j)!=(a/j)){//判断a除以y能否使用
					ans++;
				}
			}
		}
	}
	write(ans);
	return 0;
}