您的位置: 首页  >  IT文章  >  Codeforces 1154G Minimum Possible LCM

Codeforces 1154G Minimum Possible LCM

分类: IT文章 • 2025-01-19 14:57:55

题目链接：http://codeforces.com/problemset/problem/1154/G

题目大意：

　　给定n个数，在这些数中选2个数，使这两个数的最小公倍数最小，输出这两个数的下标（如果有多组解，任意输出一组即可）。

分析：

　　直接2个循环两两配对一下肯定要超时的，这里可以考虑枚举公因数，因为LCM是与最大公因数相关的，如果我们枚举了所有的公因数，那么我们就枚举了所有的LCM。

　　对于每一个公因数d，含有因子d的数从小到大排序为x1，x2，x3……xn，共有n个。

　　首先计算一下前两个数的GCD，有2种可能：

　　1：如果GCD(x1，x2) == d，那就没必要再计算GCD(xi，xj) (1 < i < j <= n)了，只要计算一下LCM(x1，x2)即可，因为如果GCD(xi，xj) == d，LCM(xi，xj)肯定大于LCM(x1，x2)；如果GCD(xi，xj) == d_ > d，LCM(xi，xj)有可能小于LCM(x1，x2)，不过这个等d枚举到了d_再算也是一样的。

　　2：如果GCD(x1，x2) == d_ > d，没必要再计算LCM(x1，x2)，可以等到枚举到d_再计算，也没必要再计算GCD(xi，xj)，因为如果GCD(xi，xj) == d，LCM(xi，xj) = xi * xj / d > x1 * x2 / d > x1 * x2 / d_ = LCM(x1，x2)；如果GCD(xi，xj) > d，也不需要。

代码如下：

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 #define Rep(i, n) for (int i = 0; i < (n); ++i)
  5 #define rRep(i, n) for (int i = (n) - 1; i >= 0; --i)
  6 #define For(i, s, t) for (int i = (s); i <= (t); ++i)
  7 #define rFor(i, t, s) for (int i = (t); i >= (s); --i)
  8 #define foreach(i, c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
  9 #define rforeach(i, c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i)
 10 
 11 #define INIT() std::ios::sync_with_stdio(false);std::cin.tie(0);
 12 #define pr(x) cout << #x << " = " << x << "  "
 13 #define prln(x) cout << #x << " = " << x << endl
 14 #define EL() printf("
")
 15 #define GL(s) getline(cin, (s))
 16 #define SHOW_VECTOR(v) {std::cerr << #v << "	:"; for(const auto& xxx : v){std::cerr << xxx << " ";} std::cerr << "
";}
 17 #define SHOW_MAP(v) {std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "
";}}
 18 
 19 template<typename T1, typename T2>
 20 istream &operator>>(istream &in, pair<T1, T2> &p) {
 21     in >> p.first >> p.second;
 22     return in;
 23 }
 24 
 25 template<typename T>
 26 istream &operator>>(istream &in, vector<T> &v) {
 27     for (auto &x: v)
 28         in >> x;
 29     return in;
 30 }
 31 
 32 template<typename T1, typename T2>
 33 ostream &operator<<(ostream &out, const std::pair<T1, T2> &p) {
 34     out << "[" << p.first << ", " << p.second << "]" << "
";
 35     return out;
 36 }
 37 
 38 #define LOWBIT(x) ((x)&(-x))
 39 
 40 #define ALL(x) x.begin(),x.end()
 41 
 42 #define ms0(a) memset(a,0,sizeof(a))
 43 #define msI(a) memset(a,inf,sizeof(a))
 44 #define msM(a) memset(a,-1,sizeof(a))
 45 
 46 #define MP make_pair
 47 #define PB push_back
 48 #define ft first
 49 #define sd second
 50 
 51 inline int gc(){
 52     static const int BUF = 1e7;
 53     static char buf[BUF], *bg = buf + BUF, *ed = bg;
 54     
 55     if(bg == ed) fread(bg = buf, 1, BUF, stdin);
 56     return *bg++;
 57 } 
 58 
 59 inline int ri(){
 60     int x = 0, f = 1, c = gc();
 61     for(; c<48||c>57; f = c=='-'?-1:f, c=gc());
 62     for(; c>47&&c<58; x = x*10 + c - 48, c=gc());
 63     return x*f;
 64 }
 65 
 66 typedef long long LL;
 67 typedef pair< int, int > PII;
 68 typedef pair< LL, LL > PLL;
 69 typedef map< int, int > MII;
 70 const double EPS = 1e-10;
 71 const double PI = acos(-1.0);
 72 const LL mod = 1e9 + 7;
 73 const LL inf = 0x7fffffff;
 74 const LL infLL = 0x7fffffffffffffffLL;
 75 const LL ONE = 1;
 76 const int maxN = 1e7 + 7;
 77 
 78 struct A{
 79     int pos;
 80     int cnt = 0;
 81 };
 82 
 83 LL n, ret = infLL;
 84 A a[maxN];
 85 PLL ans;
 86 
 87 inline LL gcd(LL x,LL y){
 88     LL t;
 89     if(!(x && y))return -1;
 90     while(y){
 91         t=x%y;
 92         x=y;
 93         y=t;
 94     }
 95     return x;
 96 }
 97 
 98 inline LL lcm(LL x,LL y){
 99     LL t = gcd(x,y);
100     if(t == -1)return -1;
101     return x/t*y;
102 }
103 
104 int main(){
105     INIT();
106     cin >> n;
107     For(i, 1, n) {
108         LL x;
109         cin >> x;
110         if(a[x].cnt == 0) {
111             a[x].pos = i;
112             ++a[x].cnt;
113         }
114         else if(a[x].cnt == 1) {
115             if(x < ret) {
116                 ret = x;
117                 ans = MP(a[x].pos, i);
118             }
119             ++a[x].cnt;
120         }
121     }
122     
123     // Enumerate common factor d
124     For(d, 1, maxN) {
125         LL x1 = 0;
126         for(int x2 = d; x2 < maxN; x2 += d){
127             if(!a[x2].cnt) continue;
128             if(!x1) x1 = x2;
129             else{
130                 // x1,x2为前2个有公因子d的数 
131                 if(gcd(x1, x2) == d){
132                     LL tmp = x2 / d * x1;
133                     if(tmp < ret){
134                         ret = tmp;
135                         ans = MP(a[x2].pos, a[x1].pos);
136                     }
137                 }
138                 break;
139             }
140         }
141     }
142     
143     if(ans.ft > ans.sd) swap(ans.ft, ans.sd);
144     cout << ans.ft << " " << ans.sd;
145     return 0;
146 }
View Code

相关推荐