P9076 [PA2018] PIN 题解
Elairin176
·
·
题解
传送门
数学好题。
首先，题目要求 b 是 a 的倍数，c 是 b 的倍数，a+b+c=n，所以 a 一定是 n 的因数。
接下来我们推一下 a,b,c 的值域。
$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：
```cpp
//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;
}
```