#219. PIN 题解

#219. PIN

时间限制：200ms

空间限制：256MB

题意简述

给定正整数 $n$，求满足以下所有条件的整数三元组 $(a,b,c)$ 的数量：

$0\lt a\lt b\lt c$；
$a+b+c=n$；
设 $b=k_1a$，$c=k_2a=k_3b$，则 $k_1,k_2,k_3$ 均为整数。

输入格式

一行一个正整数 $n$（$1\le n\le 10^9$）。

输出格式

一行一个整数，表示满足条件的三元组数量。

输入输出样例

样例输入

样例输出

说明/提示

样例解释

两个三元组分别为 $(1,2,32)$ 和 $(5,10,20)$。

探索

显然 $k_2=k_3\times k_1$。

所以 $b=k_1a$，$c=(k_1\times k_3)a$。

进一步得 $n=(1+k_1+k_1\times k_3)a$。

由于 $a\lt b\lt c$，所以 $k_1,k_3\ge 2$。

设 $k=k_1\times k_3+k_1+1$，则 $k\ge 7$。

同时，$k-1=k_1\times k_3+k_1=k_1\times(k_3+1)$，故 $k-1$ 也要能够被表示为一个不小于 $2$ 的正整数和一个不小于 $3$ 的正整数的积才行。

所以，当 $k$ 确定时，满足条件的二元组 $(k_1,k_3)$ 个数即为 $k-1$ 的因数个数减二（不是 $1\times (k-1)$）再减一（如果 $(k-1)$ 是偶数那么 $k_3+1\ge 3$）。

再来看一下样例。

$n=35=35\times 1=7\times 5$。由于这两组反过来都会有 $k\lt 7$，所以只有这两种拆分方案。

$35-1=34=2\times 17$，$7-1=6=2\times 3$，两个数都具有唯一拆法，所以答案为 $2$。

考虑首先把 $n$ 的所有因子找出来，找完后暴力枚举所有大于等于 $7$ 的因子，将他们减一后算出各自的合法拆分数就可以了。

至于时间复杂度？一个数的因子少之又少，所以根本不需要花什么时间。实际上，不考虑排序，复杂度大概为 $\sqrt{n}$ 乘上一个常数（量级与 $n$ 的因子个数相同）。~~相信自己，勇敢尝试，不断进步，让我们体验成功带来的自信，从而走向自强吧！~~

AC 代码

#include <bits/stdc++.h>
using namespace std;
#define LL long long

#define N 100007
int cnt,a[N];

inline bool check(int v,int k){//对于k3的判定
    return v!=1&&v!=k&&v!=2;
}

inline int Count(int k){//计算 k-1 的合法拆分方案数
    int res=0;
    for(int i=1;i*1ll*i<=k;i++)
        if(!(k%i)){
            res+=check(i,k);
            if(i*i!=k) res+=check(k/i,k);//注意平方数的判断（比如说9）
        }
    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    int n,ans=0;
    cin>>n;
    if(n<7){cout<<0<<'\n';return 0;}//特判：无方案
    for(int i=1;i*1ll*i<=n;i++)//根号复杂度筛因子
        if(!(n%i)){
            a[++cnt]=i;
            if(i*i!=n) a[++cnt]=n/i;
        }
    sort(a+1,a+cnt+1);//将所有因子从小到大排序
    for(int i=cnt;i&&a[i]>=7;i--)
        ans+=Count(a[i]-1);//检查每个因子是否能作为 k
    cout<<ans<<'\n';

    return 0;
}

纯纯乐子题的乐子题解，看着玩就好。如果有什么不妥之处还请批评指正。

SamHH0912的博客

博客