/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 320.0 KiB
#2 Time Exceeded ≥1068ms ≥536.0 KiB
#3 Time Exceeded ≥1093ms ≥324.0 KiB

Code

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

long long findlcm(long long a, long long b){
	long long lcm = 1;
	if(a%2 == 0 || b%2 ==0){
		lcm = lcm *2;
		if(a%2==0){
			a /= 2;
		}
		if(b%2==0){
			b /= 2;
		}
	}
	if(a%3 == 0 || b%3 ==0){
		lcm = lcm *3;
		if(a%3==0){
			a /= 3;
		}
		if(b%3==0){
			b /= 2;
		}
	}
	if(a%5 == 0 || b%5 ==0){
		lcm = lcm * 5;
		if(a%5==0){
			a /= 5;
		}
		if(b%5==0){
			b /= 5;
		}
	}
	if(a%7 == 0 || b%7 ==0){
		lcm = lcm *7;
		if(a%7==0){
			a /= 7;
		}
		if(b%7==0){
			b /= 7;
		}
	}
	lcm *= a * b;
	return lcm;
}
int findgcd(long long a, long long b){
	long long mx = max(a,b);
	long long mn = min(a,b);
	long long tmn = mn, gcd;
	while(tmn > 0){
		if(mx % tmn == 0){
			gcd = tmn;
			return gcd;
		}
		tmn--;
	}
	tmn = mn;
	while(mn > 0){
		mx = mn;
		mn = (mx % mn);
		tmn = mn;
		while(tmn > 0){
			if(mx % tmn == 0){
				gcd = tmn;
				return gcd;
			}
		tmn--;
		}
	}
}

int main(){
   int t;
   cin >> t;
   for(int i=0;i<t;i++){
   	long long a,b,lcm,gcd;
   	int pcount = 0;
   	cin >> a >> b;
   	for(long long j=1;j<=a;j++){
   		for(long long k=1;k<=b;k++){
   			gcd =  findgcd(j,k);
   			lcm = findlcm(j,k);
   			if(gcd != lcm){
   				pcount++;
   			}
   		}
   	}
   	cout << pcount << endl;
   }
	return 0;
}

Information

Submit By
Type
Submission
Problem
P1075 GCD not equal LCM
Contest
Brain Booster #5
Language
C++20 (G++ 13.2.0)
Submit At
2024-09-05 16:22:00
Judged At
2024-11-11 03:00:46
Judged By
Score
10
Total Time
≥1093ms
Peak Memory
≥536.0 KiB