当前位置:网站首页>Problem - 1646C. Factorials and Powers of Two - Codeforces
Problem - 1646C. Factorials and Powers of Two - Codeforces
2022-07-06 09:28:00 【你好_Ä】
Problem - 1646C. Factorials and Powers of Two - Codeforces
A number is called powerful if it is a power of two or a factorial. In other words, the number m is powerful if there exists a non-negative integer d such that m=2d or m=d!, where d!=1⋅2⋅…⋅d (in particular, 0!=1). For example 1, 4, and 6 are powerful numbers, because 1=1!, 4=22, and 6=3! but 7, 10, or 18 are not.
You are given a positive integer n. Find the minimum number k such that n can be represented as the sum of k distinct powerful numbers, or say that there is no such k.
Input
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤100). Description of the test cases follows.
A test case consists of only one line, containing one integer n (1≤n≤1012).
Output
For each test case print the answer on a separate line.
If n can not be represented as the sum of distinct powerful numbers, print −1.
Otherwise, print a single positive integer — the minimum possible value of k.
Example
input
4
7
11
240
17179869184
output
2
3
4
1
问题解析
这题是说,给你一个数,让你看这个数最少可以由几个2的幂(1,2,4,8等)和阶乘(1,2,6,24)等组成。
首先,每个数都必然会被组合出来,因为所有的数都可以用二进制表示,二进制下有x个1,就说明这个数可以用x个2的次幂来组成,那么我们就是要找在阶乘的组合下,能不能找到更小的x。
题目的数组范围是10^12 ,那么阶乘最大就到15!,算上0!,一共是16个数。我们可以用二进制枚举的方法来枚举(从1枚举到216,看二进制位上哪个位置有1,我们就取哪个数,这样就可以得到这16个数所有的组合)。算出合后,计算:(所用阶乘数+n减去合后用二进制取得的1个数),并维护最小值即可。时间复杂度为O(n*216 )
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 5050;
int lowbit(ll x)
{
int cnt = 0;
while (x)
{
if (x % 2 == 1)cnt++;
x /= 2;
}
return cnt;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
vector<ll>ans(16);
ans[0] = 1;
for (int i = 1; i <= 15; i++)ans[i] = ans[i - 1] * i;
int t;
cin >> t;
while (t--)
{
ll n;
cin >> n;
ll res = lowbit(n), sum = 0, cnt = 0;
for (ll i = 1; i <= (1 << 16); i++)
{
sum = 0, cnt = 0;
for (ll j = 0; j <= 15; j++)
{
if (((i >> j) & 1))
{
sum += ans[j];
cnt++;
}
}
if (sum <= n)
{
res = min(cnt + lowbit(n - sum), res);
}
}
cout << res << endl;
}
return 0;
}
边栏推荐
- Sanic异步框架真的这么强吗?实践中找真理
- Socket communication
- 1323. Maximum number of 6 and 9
- 渗透测试 ( 3 ) --- Metasploit Framework ( MSF )
- The concept of C language array
- QWidget代码设置样式表探讨
- Frida hook so layer, protobuf data analysis
- C language learning notes
- F - birthday cake (Shandong race)
- Penetration test (8) -- official document of burp Suite Pro
猜你喜欢
The "sneaky" new asteroid will pass the earth safely this week: how to watch it
读取和保存zarr文件
Information security - Analysis of security orchestration automation and response (soar) technology
Luogu P1102 A-B number pair (dichotomy, map, double pointer)
渗透测试 ( 4 ) --- Meterpreter 命令详解
(POJ - 3685) matrix (two sets and two parts)
1855. Maximum distance of subscript alignment
D - function (HDU - 6546) girls' competition
628. Maximum product of three numbers
1323. Maximum number of 6 and 9
随机推荐
Gartner: five suggestions on best practices for zero trust network access
【练习-3】(Uva 442)Matrix Chain Multiplication(矩阵链乘)
409. Longest palindrome
F - birthday cake (Shandong race)
[exercise-6] (PTA) divide and conquer
第 300 场周赛 - 力扣(LeetCode)
【练习4-1】Cake Distribution(分配蛋糕)
Advancedinstaller安装包自定义操作打开文件
【练习-8】(Uva 246)10-20-30==模拟
628. Maximum product of three numbers
1605. Sum the feasible matrix for a given row and column
QT按钮点击切换QLineEdit焦点(含代码)
QT实现窗口置顶、置顶状态切换、多窗口置顶优先关系
Vs2019 initial use
Pyside6 signal, slot
Data storage in memory & loading into memory to make the program run
The concept of C language array
Opencv learning log 24 -- Hough transform 2 (maximum interval and minimum length can be limited)
Codeforces Round #803 (Div. 2)A~C
Socket communication