试题 算法训练 整数拆分
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
对于给定的正整数S，将其拆分为正整数的升序等差数列的和的形式。 例如，对于S = 9，共有如下两种拆分方案：
9 = 1 + 3 + 5；
9 = 2 + 3 + 4
当然，并不是所有的正整数都能做到这种拆分。
输入格式
测试数据的输入一定会满足的格式。
例：输入的第一行包含两个整数n, m，分别表示矩阵的行数和列数。接下来n行，每行m个正整数，表示输入的矩阵。
输出格式
正整数S ( S<=50000000 ) 。
样例输入
样例1:
10
样例2:
3
样例输出
样例1:
1
样例2:
0
提交代码：
#include <iostream> #include <cmath> using namespace std; int i = 1, j = 1; int main() { int s; cin >> s; s = s * 2; int sum = 0; for (i = 3; i <= (int)sqrt(s); i++) //枚举项数 { if (s % i == 0) { int t = s / i; //首尾项的和 for (j = 1; j <= t / (i - 1); j++) //枚举公差 { if ((t + (i - 1) * j) % 2 != 0) continue; int an = (t + (i - 1) * j) / 2; int a1 = t - an; if (a1 > 0 && an > 0) sum++; } } } cout << sum << endl; return 0; }
