UVA11417& UVA11461

點我看UVA11417

解題思路

這題只要寫出GCD函式再代入題目要的迴圈即可
利用輾轉相除法求出GCD，
它可以很快地求出最大公因數(GCD)的方法。
原理是兩個數字互相減來減去，最後就會剩下最大公因數。

延伸參考連結:https://www.csie.ntu.edu.tw/~b98902112/cpp_and_algo/cpp02/euclidean_algorithm.html

解法一

自己寫出gcd函式

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

//利用遞迴讓 被除數(a)、除數(b) 互換
int gcd( int a, int b )
{
    if( b==0 )
        return a;
    return gcd( b, a%b );
}

int main()
{
 int N,i,j ;
 while(cin>>N)
 {
  if(N==0)break;
  int G=0;

for(i=1;i<N;i++)
{
for(j=i+1;j<=N;j++)

{

      G+=gcd(i,j);

}

}
cout<<G<<endl;
 }
return 0;
}

解法二

相信大多數人都不知道C++有內建gcd這個函式庫，因此今天使用第2解法來展示給各位看
-->運用 algorithom 的gcd函式

#include<iostream>
#include<algorithm>
using namespace std;

int main(){
 int n,g;
 
 while(cin>>n){
  if(n==0) break; //n=0跳出 
  g=0;
  
  for(int i=1;i<n;i++){
   for(int j=i+1;j<=n;j++){
    g += __gcd(i,j); //用C++中內建的__gcd( , )函式 
   }
  }
  cout<<g<<endl;
 }
}

UVA11461

點我看UVA11461

解題思路

計算a至b之間的完全平方數

#include <iostream>
#include <cmath>

using namespace std;

int main(){
	int a,b;
	bool t[100001]={false};
	
	for(int i=0;i*i<100001;i++){
		t[i*i]=true;
	}
	while(cin>>a>>b&&a!=0){
		int count=0,sum=0;
		
		for(int i=a;i<=b;i++){
			if(t[i])count++;
		}
		
		
		cout<<count<<endl;
	
	}
}