关于连续自然数和问题:
以下为我的c++代码,前面的“/* */”注释里的是我的暴力枚举代码,后面的是还有点bug的优化代码,样例不能过,求调!
思路是分解质因数,其他我感觉无需多说。
#include <bits/stdc++.h>
using namespace std;
const int maxa=2*1e6+10;
//配套蒟蒻函数
/*
int su(int a,int b)
{
return a*(a+1)/2-(b-1)*b/2;
}
*/
//70分暴力枚举(蒟蒻专用)
/*
int main()
{
int n;
cin>>n;
for(int i=1;i<=n/2+1;i++)
{
for(int j=i;j<=n/2+2;j++)
{
if(su(j,i)==n)
{
cout<<i<<" "<<j<<endl;
break;
}
}
}
return 0;
}
*/
//优化,不择手段地优化! (分解只因数法)
bool prime[maxa];
int ap[maxa],qc[maxa]={0,2},len=0;
void getPrime(){
memset(prime, true, sizeof(prime));
prime[0] = prime[1] = false;
for(int i=2; i<sqrt(maxa); i++){
if(prime[i] == true){
for(int j=i+i; j<maxa; j+=i){
prime[j] = false;
}
}
}
}
void getFactor(int n){
for(int i=2; i<=n; i++){
while(n%i == 0){
n /= i;
ap[++len] = i;
}
}
}
int main()
{
int n;
cin>>n;
getFactor(n);
int l=1;
for(int i=1;i<=len;i++)
{
if(qc[l]!=ap[i])
qc[++l]=ap[i];
}
// cout<<endl<<"------test00000------"<<endl;
// for(int i=1;i<=l;i++)
// cout<<qc[i]<<" ";
// cout<<endl;
float mid;
for(int i=l;i>=1;i--)
{
mid=1.0*n/qc[i];
// cout<<endl<<"-----------------test------------------"<<endl<<i<<"/"<<l<<" "<<mid<<endl<<"--------------------------------end_test----------------------------"<<endl;
if(mid*2==(int)(mid*2))
{
if((mid-1.0*(qc[i]-1)/2>=0)&&(mid-1.0*(qc[i]-1.0)/2.0!=mid+1.0*(qc[i]+1.0)/2.0-1.0))
{
if(mid-1.0*(qc[i]-1.0)/2.0*2==int(mid-1.0*(qc[i]-1.0)/2.0*2))
cout<<mid-1.0*(qc[i]-1.0)/2.0<<" "<<mid+1.0*(qc[i]+1.0)/2.0-1.0<<endl;
}
else
continue;
}
}
return 0;
}