3025. 连续正整数之和

ccccc
#include <bits/stdc++.h>
using namespace std;

int main(){
    int T; scanf("%d",&T);
    for(int cas=0;cas<T;cas++){
        int n=0,ans=0,min_diviso=0;
        scanf("%d",&n);
        for(int i=1;i<=(int)sqrt(n);i++){if(n%i==0){min_diviso=i;break;} }
        for(int i=2;i<=(n/min_diviso);i++){//假设n能分成i个整数
            if(i%2==0){//i是偶数:如果n除i以“0.5”结尾且n/i范围合法,n能分成连续i个整数
                if((n+i/2)%i==0&&(n/i)>=(i/2))
                    ans++;
            }
            else{//i是奇数:如果i整除n且n/i范围合法,n能分成连续i个整数
                if(n%i==0&&(n/i)>=(i+1)/2)
                    ans++;
            }
        }
        printf("case #%d:\n%d\n",cas,ans);
    }
    return 0;
}
10175102262 LarsPendragon

不需要n==3的算法(Python注意, 运行时间0.024)

from math import sqrt
T=int(input())
for I in range(T):
    n=int(input())
    count=0
    for i in range(2, int(sqrt(2*n))+1, 2):
        if n%i==i/2:
            count+=1
    for j in range(3, int(sqrt(2*n))+1, 2):
        if n%j==0:
            count+=1
    print("case #%d:\n%d"%(I, count))
150042

可以计算n所有除2的倍数(如果有的话)外,因子的个数

DLIU

关于
给定一个正整数N,判断其是否可以表示为一组连续正整数的和
的思考。

//自己的一点想法…可能会有错误,且不太精准,欢迎指正。

可以分为2x2个决定元素,共四种情况。
元素1:分成的份数(part)是否为偶数
元素2:N除以part后的余数的大小。

在此引入一个概念:偏移量。因为上述运算为整形运算,在N/part后会得到一个势必处于所求连续正整数(假如满足条件)中的整数,将该整数称为基数。(基数的part倍)小于等于N,与N的差为(0,part),将所求的差叫做偏移量。

如:N=24,part=5,则偏移量为4,假设所求的连续正整数串存在,则其必定与5,6,7,8,9这个连续正整数串存在关系。将数串中的元素同加减任意整数(条件是保证基数仍在数串内),则必定能得到指定数串。
该数串的和为N。 若偏移量除以part无余数,且平移的值(商)小于等于part-1,则可以通过加减来使其在数轴上平移的方式来使该数串成立。
这样做的话可以减少很多特判。且运算量可以接受。

example:

N = 9,part = 3 -> 3 4 5,offset = 3.
此时offset%part==0,offset/part=1,故成立。

N = 21, part = 4 ->4,5,6,7 offset = 1. 故不成立。

附上代码中重要片段:

bool couldbeput(const int test,const int part){
int result=test/part;
result=resultpart+part(part-1)/2;
int offset=test-result;
if(abs(offset)%abs(part)==0)
return true;
else
return false;

}
for(int i=2;i<(int)(sqrt(2*test+1)+1);i++)
if(couldbeput(test,i))

在最后决定i的范围时处理得很草率,,,但好歹ac了。

DLIU

中途粘贴时有格式问题,照搬会有语法错误。

10195101422

假定两个连续数
2x+1=A
x=(A-1)/2-------------A 为奇数即可
假定 3 个连续:3x+3=A
x=(A-3)/3-----------A 能被 3 整除
假定 4 个连续:4x+6=A
x=(A-6)/4----------A-6 能被 4 整除
.5..:5x+10=A
x=(A-10)/5--------A-10 能被 5 整除

找规律。。。

欢迎访问我的主页!http://godweiyang.com

为什么WA,有何问题???
n = 3时你算出来是2,实际上是1,加一个if(n == 3)就通过了

你当前正在回复 博客/题目
存在问题!