题目:
Little C loves number ?3? very much. He loves all things about it.
Now he has a positive integer nn. He wants to split nn into 3positive integers a,b,ca,b,c, such that a+b+c=na+b+c=n and none of the 3 integers is a multiple of 3. Help him to find a solution.
- Input
- A single line containing one integer nn (3≤n≤10^9) - the integer Little C has.
- Output
- Print 3 positive integers a,b,c in a single line, such that a+b+c=nand none of them is a multiple of 3
- It can be proved that there is at least one solution. If there are multiple solutions, print any of them.
- Examples
- input
- 3
- output
- 1 1 1
- input
- 233
- output
- 77 77 79
题意分析:
这题是一个比较单纯的数学题目, 给你一个数 n, 你需要把他分解成 3 个数,, 并且这 3 个数都不是 3 的倍数.
这题我想的是根据数的素数分解原理, 因为每个数都可以表示成素数相乘. 所以对于 N,
如果 N 的素因子中没有 3, 那么我们另外两个数只要相加等于 3 的倍数, 那么就一定是满足的.
如果 N 的素因子中有 3, 那么此时, 3 应该还有个最大幂指数 t, 并且 3 的 t 次幂是 N 的一个因子. 现在就是对 3 的 t 次幂的分解. 假设 b = N/(3^t)
对 3 的 t 次幂分解成 3 个不被 3 整除的数还是比较简单的, 因为是 3 的次幂, 所以肯定可以分解成 3 个 3 的 (t-1) 次幂, 那么 其中任意两个数减去 1, 另外一个数加上 1 就满足了, 再把这 3 个数都乘以 b 即满足.
代码:
- #include <iostream>
- #include <cstdio>
- using namespace std;
- int main()
- {
- int N;
- while(~scanf("%d", &N))
- {
- int cnt = 1;
- if(N%3 != 0) //N 不是 3 的倍数
- {
- printf("%d %d %d\n", 1, 2, N-3);
- continue;
- }
- while(N%3 == 0) // 提取 N 中 3 的 t 次幂因子.
- {
- cnt*=3;
- N/=3;
- }
- int a, b, c, d;
- d = cnt/3;
- if(d%3==0)
- {
- a = (d-1)*N;
- b = (d+2)*N;
- c = (d-1)*N;
- }
- else //d==1
- {
- a = b = c = d*N;
- }
- printf("%d %d %d\n", a, b, c);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2778075.html