#P2986. Non-Squarefree Numbers

    ID: 2107 传统题 1000ms 512MiB 尝试: 547 已通过: 208 难度: 6 上传者: 标签>CF1900普及+/提高-二分答案莫比乌斯函数线性筛容斥原理补集计数交换求和顺序

Non-Squarefree Numbers

题目描述

一个正整数 kk 被称为 squarefree,如果它没有一个 D2(D>1)D^2(D>1) 这样的约数。

输入格式

读入一个正整数 nn。

输出格式

找出第 nn 个不是 squarefree 的数。

样例输入 1

10

样例输出 1

27

提示

前 1010 个非 squarefree 的数:4,8,9,12,16,18,20,24,25,274,8,9,12,16,18,20,24,25,27。

数据规模与约定

对于 100%100 \% 的数据,1≤n≤10101\leq n \leq 10^{10}。