51nod 1061 最复杂的数V2
题目链接
51nod 1061
题面简述
求\([1, n]\)中约数个数最多的数。
\(n \le 10^{200}\)
题解
首先,答案一定是一个反素数。
什么是反素数?
一个正整数\(x\)是反素数的充要条件是:\([1, x - 1]\)中的整数的约数个数都小于\(x\)的约数个数。
反素数有什么性质?
把一个反素数分解成\(p_1^{a_1}p_2^{a_2}...p_n^{a_n}\)的形式,则\(a_1 \ge a_2 \ge ... \ge a_n\)。
除\(1\)以外,一个反素数\(x\)一定可以由一个小于\(x\)的反素数乘上一个质数得来。(证明大概比较显然?感性理解一下 = =)
如果我们能求出\(10^{200}\)以内所有反质数,询问时直接lower_bound即可。
由此设计出算法:
维护一个堆,一开始只放\(1\)进去;
每次取堆中最小的数(堆顶元素);
判断这是不是一个反素数:根据定义,如果比它小的反素数中有约数个数与它相等或更多的,则它不是反素数。维护当前已经出堆的反素数的约数个数的最大值,如果当前堆顶元素的约数个数不比它大,则它不是反素数。
枚举各个合法的素数(要求满足性质1)和它相乘,如果没有超出\(10^{200}\)则也压到堆中。
这样就能求出\(10^{200}\)以内所有反质数了(实际上只有3810个!)
这道题需要高精度,好在只需要高精度乘低精度即可。
AC代码
#include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <iostream> #include <queue> #define space putchar(' ') #define enter putchar('\n') using namespace std; typedef long long ll; template <class T> void read(T &x){ char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } template <class T> void write(T x){ if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10); } const int N = 1000005, maxp = 100; int T, prime[N], pcnt, tot; bool np[N]; char s[256]; struct big { ll n[256], l; big(){ memset(n, 0, sizeof(n)); n[1] = l = 1; } void out(){ for(int i = l; i; i--) write(n[i]); } bool operator < (const big &b) const { if(l != b.l) return l < b.l; for(int i = l; i; i--) if(n[i] != b.n[i]) return n[i] < b.n[i]; return 0; } bool operator > (const big &b) const { if(l != b.l) return l > b.l; for(int i = l; i; i--) if(n[i] != b.n[i]) return n[i] > b.n[i]; return 0; } big operator * (ll x) const { big c; c.l = l; for(int i = 1; i <= l; i++) c.n[i] = n[i] * x; while(x) c.l++, x /= 10; for(int i = 1; i <= c.l; i++) c.n[i + 1] += c.n[i] / 10, c.n[i] %= 10; while(!c.n[c.l]) c.l--; return c; } } MAX, cur; struct data{ big num; int cnt[maxp]; data(){ memset(cnt, 0, sizeof(cnt)); } data(big x){ num = x; memset(cnt, 0, sizeof(cnt)); } bool operator < (const data &b) const{ return num > b.num; } data operator * (int p) const{ data c; c.num = num * prime[p]; memcpy(c.cnt, cnt, sizeof(cnt)); c.cnt[p]++; return c; } } lst[4005]; priority_queue <data> que; void euler(int n){ np[0] = np[1] = 1; for(int i = 2; i <= n; i++){ if(!np[i]) prime[++pcnt] = i; for(int j = 1; j <= pcnt && i * prime[j] <= n; j++){ np[i * prime[j]] = 1; if(i % prime[j] == 0) break; } } } int main(){ euler(1000000); MAX.l = 201; MAX.n[201] = MAX.n[1] = 1; cur.n[1] = 0; que.push(data()); while(!que.empty()){ data u = que.top(); que.pop(); big d; for(int p = 1; u.cnt[p]; p++) d = d * (u.cnt[p] + 1); if(!(cur < d)) continue; lst[++tot] = u; cur = d; for(int p = 1; p < maxp && (p == 1 || u.cnt[p - 1]); p++) if((p == 1 || u.cnt[p] < u.cnt[p - 1])){ data v = u * p; if(v.num < MAX) que.push(v); } } reverse(lst + 1, lst + tot + 1); read(T); while(T--){ scanf("%s", s + 1); big n; n.l = strlen(s + 1); for(int i = 1; i <= n.l; i++) n.n[n.l - i + 1] = s[i] - '0'; data v = data(n); data u = *lower_bound(lst + 1, lst + tot + 1, v); big d; for(int p = 1; u.cnt[p]; p++) d = d * (u.cnt[p] + 1); u.num.out(), space, d.out(), enter; } return 0; }
相关推荐
liangds 2018-11-30
zzpdljd 2018-11-20
heshanking 2011-04-12
软件设计 2017-05-05
CloudXli 2020-06-11
baike 2020-01-04
hiKirin 2013-03-09
BITSKY 2019-03-29
浪漫老猫 2018-11-27
lundongcai 2018-11-22
assastor 2018-05-02
cairencong 2018-01-23
sharkandshark 2017-04-14
wlpython 2018-09-27
crqzcbk 2011-08-02
BitTigerio 2018-05-13
BitTigerio 2018-04-06