题解 | #游游的整数拆分#
游游的整数拆分
https://ac.nowcoder.com/acm/problem/255369
首先注意到两数乘积是3的倍数至少需要其中一个数的3的倍数，随便列举几个数：
3：无解
4：3+1,1+3
5：3+2,2+3
6：3+3
7：3+4,6+1,4+3,1+6
8：3+5,6+2,5+3,2+6
9：3+6,6+3
发现可以枚举其中一个数是三的倍数的方案，因为另一个数也需要是正整数(至少为1)所以方案数为(n - 1) / 3。然后发现如果n不是3的倍数的话交换a, b方案数乘2，但是如果n是3的倍数会使得交换a, b也是考虑过的方案，所以当n不是3的倍数时答案乘2。
#include<iostream>
using namespace std;
int main() {
long long n;
cin >> n;
long long ans = (n - 1) / 3;
if (n % 3) ans *= 2;
cout << ans;
return 0;
}
查看20道真题和解析
