標題
H-最小互質數
題目
我們定義兩個數的互質數當且僅當gcd(a, b) = 1，
現在L手里有n個數，分別為a1，a2，a3 ……an-1，an ，
問，沒有在這n個數中出現過并且與這n個數都互質的最小的數是多少，
LL覺得這個問題太簡單了，于是她把這個問題交給你來解決，
輸入
第一行一個數n (1 ≤ n, ai ≤ 10^5)
接下來n行，每行一個數，分別代表a1，a2，a3 ……an-1，an ，
輸出
輸出一行代表答案
樣例輸入 Copy
5
1
2
3
4
5
樣例輸出 Copy
7
提示
沒有在這n個數中出現的數有：6，7，……
6與2， 3， 4不互質，最小的與這n個數互質的數就是7了，
題目大意
輸入n個數，輸出一個與這些數都不互質的數；
思路
用一個陣列來標記出現過的數以及這個數的因子，如果輸入的數沒有1則直接輸出1,，否則用一個for回圈輸出標記陣列第一個沒有被標記的數，（代碼如下）
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
int vis[N];
int main()
{
int n;
cin >> n;
int flag = 0;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
if (x == 1)
{
flag = 1;
continue;
}
vis[x]=1;
for (int j = 2; j * j <= x; j++)
{
while (x % j == 0)
{
x /= j;
vis[j] = 1;//標記這個數的因子
}
}
vis[x] = 1;//標記這個數因子
}
if (flag==0) cout<<"1"<<endl;
else
{
for (int i = 2; i <= N; i++)
{
if (vis[i]==0)
{
cout << i << endl;
return 0;
}
else
{
for (int j = 2; j * i <= N; j++)
{
vis[i * j] = 1; //標記這個數倍數
}
}
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/278548.html
標籤：其他