题目描述
有N个正整数,求这N个正整数两两之间的最小公倍数之和。
输入说明
第1行 正整数N(N<=100)。
第2行 N个用空格分隔的正整数(每个正整数不超过10000)。
输出说明
输出这N个正整数两两之间的最小公倍数之和,结果对1000000007取模。
输入样例
4
2 3 7 6
输出样例
95
两个数的最小公倍数记为lcm(a,b),两个数最大公约数记为gcd(a,b)。
辗转相除法求最小公约数
有a*b=gcd(a,b)*lcm(a,b)
#include<iostream> #include<cstdio> #include<iomanip> #include<cstdlib> #include <algorithm> #include<string.h> #include<set> #include<math.h> #define llu unsigned long long using namespace std; int gcd(int x,int y) { if(y==0)return x; else return gcd(y,x%y); } int lcm(int x,int y) { return x*y/gcd(x,y); } int a[110]; llu s=0; int main() { //cout << fixed << setprecision(0); //cout << setw(8) << setiosflags(ios::left); int n; cin >> n ; for(int i=0;i<n;i++) cin >> a[i] ; for(int i=0;i<n-1;i++) for(int j=i+1;j<n;j++) { llu x=lcm(a[i],a[j])%1000000007; s=(s+x)%1000000007; } cout << s << endl ; return 0; }