7809

2023-10-07 05:41| 来源: 网络整理| 查看: 265

链接：http://oj.hzjingma.com/p/7809?view=classic 来源：竞码编程

题目描述求所有 2 2 2 到 n n n 的整数中，因数个数第 k k k 少的数因数个数是多少。输入描述第一行两个正整数 n n n , k k k 即题目描述中的 n n n , k k k 。输出描述输出仅一行，即因数个数第 k k k 少的数因数个数。输入 10 5 输出 3

解法一：直接暴力求解， s q r t ( n ) sqrt(n) sqrt(n) 判断因子个数。复杂度 O ( n √ n ) O(n√n) O(n√n)，对于此题目来说会 T L E TLE TLE 。

#include using namespace std; typedef long long ll; const int maxn = 2e7 + 10; ll cnt[maxn]; sets; ll cal(int x) { ll cnt1 = 2; if(x == 1) return 1; for(ll i = 2; i * i if(i * i == x) cnt1++; else cnt1 += 2; } } return cnt1; } int main() { int n, k; scanf("%d%d", &n, &k); for(int i = 2; i if (op == '-') neg = -1; op = getchar(); } while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); } return neg * x; } inline void print(int x) { if (x int n, k; n = read(); k = read(); if(n >= maxn) puts("2"); else { for(int i = 2; i 0, 1}, times[maxn], prime[maxn], num1[maxn]; //最小质因子出现次数 bool is_prime[maxn]; inline int read() { int x = 0, neg = 1; char op = getchar(); while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); } while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); } return neg * x; } inline void print(int x) { if (x for(int i = 2; i cnt[i] = 2; times[i] = 1; prime[num++] = i; } for(int j = 0; j //当前素数是最小质因子 times[i * prime[j]] = times[i] + 1; cnt[i * prime[j]] = cnt[i] / (times[i] + 1) * (times[i * prime[j]] + 1); break; } times[i * prime[j]] = 1; cnt[i * prime[j]] = cnt[i] * 2; } } } int main() { solve(); int n, k; n = read(); k = read(); if(n >= maxn) puts("2"); else { //for(int i=2;i print(i); break; } } } return 0; }

【本文地址】

7809

7809

今日新闻

推荐新闻