Codeforces 1174C Ehab and a Special Coloring Problem

青旅半醒 2021-11-04 13:34 166阅读 0赞

题目链接：[http://codeforces.com/problemset/problem/1174/C][http_codeforces.com_problemset_problem_1174_C]

![1696897-20190604122856410-947279851.png][]

--------------------

题意：给你一个n，要你填充 下标由2 ~ n 的数组**a**i，要求下标互质的俩个数不能相等，并且数组中最大值最小化。

思路：打个素数表，每个质数肯定互质所以我们令第一个质数为1，第二个质数为2...依次类推，然后根据 [算术基本定理][Link 1] ，合数就让它等于第一个分解的质数啦。

AC代码：

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int MAXN= 2e5 +5;
     4 int vis[MAXN];
     5 int a[MAXN];
     6 int n;
     7 void init()
     8 {
     9     vis[0] = 1;
    10     vis[1] = 1;
    11     for(int i = 2;i < MAXN;i ++)
    12     {
    13         if(! vis[i])
    14         {
    15             vis[i] = 0;
    16             for(int j = 2*i;j <= MAXN; j += i)
    17             {
    18                 vis[j] = 1;
    19             }
    20         }
    21     }
    22 }
    23 int gcd(int a,int b)
    24 {
    25     if(b == 0)
    26     return a;
    27     else return gcd(b,a%b);
    28 }
    29 int main()
    30 {
    31     int n;
    32     scanf("%d",&n);
    33     memset(vis,0,sizeof(vis));
    34     init();
    35     int cnt = 1;
    36     for(int i = 2;i <= n;i++)
    37     {
    38         if(!vis[i]) a[i] = cnt++;
    39         else
    40         {
    41             for(int j = 2;j <= i;j++)
    42             {
    43                 if(gcd(i,j) != 1)
    44                 {
    45                     a[i] = a[j];
    46                     break;
    47                 }
    48             }
    49         }
    50     }
    51     for(int i = 2;i <= n;i++)
    52     {
    53         printf("%d ",a[i]);
    54     }
    55     return 0;
    56 }

转载于:https://www.cnblogs.com/Carered/p/10972854.html

[http_codeforces.com_problemset_problem_1174_C]: http://codeforces.com/problemset/problem/1174/C
[1696897-20190604122856410-947279851.png]: /images/20211104/3817208be045411691ac023a128dd692.png
[Link 1]: https://baike.baidu.com/item/%E7%AE%97%E6%9C%AF%E5%9F%BA%E6%9C%AC%E5%AE%9A%E7%90%86/10920095