P1592 【互质】题解

· · 题解

遇到题没有思路怎么办，我个人喜好是要先看此题的标签。这道题有一个对我们有用的标签，那就是“数论数学”。

这类问题多半是要推导公式。对于推导公式，像我这样的蒟蒻比较倾向于先手打个表，然后找规律。

与 5  互质的数有 ：
1  2  3  4 
6  7  8  9 
11 12 13 14 
16 17 18 19
······
与 10 互质的数有 ：
1  3  7  9 
11 13 17 19 
21 23 27 29
31 33 37 39
······
与 25 互质的数有 ：
0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 
40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
······

不难发现，以上的“与 n 互质的数都有一定的周期”，那周期是多少呢？可以看出，最小正周期就是第一个输入的数 n 。

剩下的都相对简单了，判断一个数和 n 是否互质，用一个叫做最大公约数的函数，判断它是否等于一就可以了。

因为题目要求输出第k个数，所以可以先把所有小于 n 且与 n 互质的数存在一个数组（因为k和需要输出的值都小于n）。


由上述推导过程发现的规律可以得出式子：

k - 1/r * n + a[(k - 1) % r + 1]

其中，k - 1/r * n 是第 k 个数所在的周期数。

a[] 是我们打表用的数组。

a[(k - 1) % r + 1] 是找到在本周期里我们要求的数是第几个。

标程如下（已AC请放心食用）：

#include <algorithm>//最大公约数函数必备头文件 
#include <iostream>
using namespace std;
int a[10010000];//这么大的数组建议定义在全局，连初始化都省了 
int round(int k , int r , int n){ 
    return (k - 1) / r * n + a[(k - 1) % r + 1];
}
int main()
{
    int n , k , r;cin >> n >> k; 
    for(int i = 1;i < n;i ++)//打表 
        if( __gcd(i,n) == 1) r ++ , a[r] = i ;
    int ans = round(k,r,n);
    cout << ans << endl;
    return 0;
}

这样的题目，理解起来岂不是比抄更有意义？

第二篇题解祭。

管理员辛苦了。

也还请大神们多多指教。