CF409F 000001-找规律+打表

题目描述:

根据样例数据找出规律,并根所找到的规律求出数列中的第n个数

CF409F

Solution

观察样例数据可得,原数列的规律如下(此处参考OEIS上的解释,题目名称000001就是OEIS上的数列IDa000001)

From Mitch Harris, Oct 25 2006: (Start)

For p, q, r primes:
a(p) = 1, a(p^2) = 2, a(p^3) = 5, a(p^4) = 14, if p = 2, otherwise 15.
a(p^5) = 61 + 2p + 2gcd(p-1,3) + gcd(p-1,4), p>=5, a(2^5)=51, a(3^5)=67.
a(p^e) ~ p^((2/27)e^3 + O(e^(8/3)))
a(pq) = 1 if gcd(p,q-1) = 1, 2 if gcd(p,q-1) = p. (p < q)
a(pq^2) = one of the following:
* 5, p=2, q odd,
* (p+9)/2, q=1 mod p, p odd,
* 5, p=3, q=2,
* 3, q = -1 mod p, p and q odd.
* 4, p=1 mod q, p > 3, p != 1 mod q^2
* 5, p=1 mod q^2
* 2, q != +/-1 mod p and p != 1 mod q,
a(pqr) (p < q < r) = one of the following:
* q==1 mod p r==1 mod p r==1 mod q a(pqr)
* No……….No……….No……….1
* No……….No……….Yes………2
* No……….Yes………No……….2
* No……….Yes………Yes………4
* Yes………No……….No……….2
* Yes………No……….Yes………3
* Yes………Yes………No……….p+2
* Yes………Yes………Yes………p+4 (table from Derek Holt) (End)
a(n) = A000688(n) + A060689(n).

                                        - [R. J. Mathar](http://oeis.org/wiki/User:R._J._Mathar), Mar 14 2015 

因为题目描述中说,1 ≤ _n_ ≤ 64 所以我们可以直接打表

Code

1
2
3
4
5
6
7
8
9
#include<cstdio> 
const int a[]{0, 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51, 1, 2, 1, 14, 1, 2, 2, 14, 1, 6, 1, 4, 2, 2, 1, 52, 2, 5, 1, 5, 1, 15, 2, 13, 2, 2, 1, 13, 1, 2, 4, 267, 1, 4, 1, 5, 1, 4, 1, 50, 1, 2, 3, 4, 1, 6, 1, 52, 15, 2, 1, 15, 1, 2, 1, 12, 1, 10, 1, 4, 2};

int main(){
int n;
scanf("%d",&n);
printf("%d",a[n]);
return 0;
}