a059: 完全平方和

2022.11.30 PM 09:00 by CBJ

來源 : https://zerojudge.tw/ShowProblem?problemid=a059
出題者 : 雄中公假社
標籤 : 數學、枚舉法
難易度 : 1

解題想法 : 
題目是要在a~b之間找出完全平方數，最直接的方法當然是從a走到b，並判斷是否為完全平方數，但因為完全平方數並不多，所以我們可以換個角度來想，改成枚舉1~32的平方，並判斷是否在a~b的範圍內即可(若小於a則continue，若大於b則break)

只枚舉1~32的原因是因為，題目有提到值不會大於1000，而32*32 = 1024 > 1000，故枚舉到32即可。

如此一來即可從最多枚舉1001次改成最多枚舉32次，大幅提升了執行效率。

//C language

#include<stdio.h>
int main(){
    int T;
    scanf("%d",&T);
    for(int i=1;i<=T;i++){
        int a,b,cnt=0;
        scanf("%d%d",&a,&b);
        for(int k=1;k<=32;k++){ 
            if(k*k < a)continue;
            if(k*k > b)break;
            cnt+=k*k;
        }
        printf("Case %d: %d\n",i,cnt);
    }
    return 0;
}

//C++ language

#include<iostream>
using namespace std;
int main(){
    int T; cin>>T;
    for(int i=1;i<=T;i++){
        int a,b,cnt=0; cin>>a>>b;
        for(int k=1;k<=32;k++){
            if(k*k < a)continue;
            if(k*k > b)break;
            cnt+=k*k;
        }
        cout<<"Case "<<i<<": "<<cnt<<"\n";
    }
    return 0;
}

## Python language

T=int(input())
for i in range(1,T+1):
    a=int(input())
    b=int(input())
    cnt=0
    for k in range(1,32+1):
        if k**2<a: continue;
        if k**2>b: break;
        cnt+=k**2;
    print(f"Case {i}: {cnt}")

相關文章

分享此文：