题意:求出所有的情况,等差上去可以达到 m 值。
原来想着暴力搜索,但是题中的数据太大,所以时间超限。
百度了一下,发现可以套公式。
等差求和公式:
Sn=(a1+aN)*n/2
=(a1+a1+d(n-1))*n/2
=a1*n+d(n-1)*n/2;
因为此处公差 d=1,所以 Sn=a1*n+(n-1)*n/2, 当从第一项开始算起时(因本题首项为 1,即 a1=1 时),Sn=M 时的项的个数 n 最多;
a1=1,现在又可化简为 Sn=n+(n-1)*n/2=(n+1)n/2;
由题意得 M=Sn,N 为项的个数,则 N<=n(max)=sqrt(Sn*2)=sqrt(M*2);
因此原式 M=Sn =a1*n+(n-1)n/2=a1*N+(N-1)N/2, 可得 a1*N=M-(N-1)N/2;
数据都已经全了,现在只要遍历 n(max) 以内项数中,Sn=M 的个数即可。
那么如何判断 Sn=M 呢?也就是判断 a1*N=Sn-(N-1)N/2; 得到的 a1*N 这个数能否被 N 整除,因为整除的话,说明首项存在于序列
- #include#include int main() {
- int N,
- M,
- i,
- n,
- m;
- while (scanf("%d%d", &N, &M) != EOF) {
- if (N == 0 && M == 0) break;
- n = sqrt((double)(M) * 2);
- while (n) {
- m = M / n - (n - 1) / 2;
- if (m * n + (n * (n - 1) / 2) == M) printf("[%d,%d]\n", m, m + n - 1);
- n--;
- }
- printf("\n");
- }
- return 0;
- }
来源: