P1147 連續自然數和（數論，洛谷，java）

洛谷連結：https://www.luogu.com.cn/problem/P1147

1.暴力解法

import java.util.Scanner;
public class Main {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in=new Scanner(System.in);
        int M=in.nextInt();
        
        for(int i=1;i<=M/2;i++) {   //注意i=1
        	int sum=0;              //每次要清0
        	for(int j=i;j<=M;j++) {
        		sum+=j;
        		if(sum==M) {
        			System.out.println(i+" "+j);
        		}
        		if(sum>=M) { break; }  //不退出很耗時
        	}
        }
	}
}
           

2.數論解法

設首項為L，末項為R，那麼sum(L,R)=(L+R)(R-L+1)/2=M

即(L+R)(R-L+1)=2M

可以把2M分解成兩個數之積，假設分成了兩個數K1,K2，且K1<K2時，

可以列一個二進制一次方程組

R-L+1=K1

L+R=K2 解得L=(K2-K1+1)/2, R=(K1+K2-1)/2

當K1,K2一奇一偶時，L,R才有自然數解.

不過有一種特殊情況，就是L=R的情況，這種情況是不允許的

即(K2-K1+1)/2≠(K1+K2-1)/2,解得K1≠1

import java.util.Scanner;
public class Main {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in=new Scanner(System.in);
        int M=in.nextInt();
        
        for(int k1=(int) Math.sqrt(2*M);k1>1;k1--) {  //枚舉k1(注意是k1>1而不是k1>=1)
        	if(2*M%k1==0  &&  (k1+2*M/k1)%2==1) {   //如果K2是整數而   且   k2與K1一奇一偶
        		int k2=2*M/k1;
        		System.out.println((k2-k1+1)/2+" "+(k1+k2-1)/2);
        	}
        }
	}
}