当前位置:网站首页>Problem - 1646C. Factorials and Powers of Two - Codeforces
Problem - 1646C. Factorials and Powers of Two - Codeforces
2022-07-06 16:14:00 【Hello_ Ä】
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
Problem analysis
The question is , Give you a number , Let me show you how many this number can be at least 2 The power of (1,2,4,8 etc. ) And factorial (1,2,6,24) Other components .
First , Every number must be combined , Because all numbers can be expressed in binary , There is x individual 1, It shows that this number can be used x individual 2 To the power of , So we are looking for the combination of factorials , Can you find something smaller x.
The array range of topics is 10^12 , Then the factorial maximum is 15!, You count 0!, Is the total 16 Number . We can use binary enumeration method to enumerate ( from 1 Enumerate to 216, See which position on the binary bit has 1, Let's take whichever number , So you can get this 16 Number all combinations ). Calculate the sum , Calculation :( Order multiplier used +n After subtracting and combining, it is obtained in binary 1 Number ), And maintain the minimum value . The time complexity is O(n*216 )
AC Code
#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;
}
边栏推荐
- 计算时间差
- Radar equipment (greedy)
- 滲透測試 ( 1 ) --- 必備 工具、導航
- Gartner: five suggestions on best practices for zero trust network access
- C language is the watershed between low-level and high-level
- Web based photo digital printing website
- 7-1 understand everything (20 points)
- Effet d'utilisation, déclenché lorsque les composants de la fonction sont montés et déchargés
- Perform general operations on iptables
- 628. Maximum product of three numbers
猜你喜欢
(POJ - 3579) median (two points)
Advancedinstaller安装包自定义操作打开文件
Nodejs+vue online fresh flower shop sales information system express+mysql
The "sneaky" new asteroid will pass the earth safely this week: how to watch it
Gartner: five suggestions on best practices for zero trust network access
Information security - Analysis of security orchestration automation and response (soar) technology
Candy delivery (Mathematics)
Openwrt source code generation image
渗透测试 2 --- XSS、CSRF、文件上传、文件包含、反序列化漏洞
[teacher Gao UML software modeling foundation] collection of exercises and answers for level 20 cloud class
随机推荐
QT实现圆角窗口
图图的学习笔记-进程
C language must memorize code Encyclopedia
Problem - 922D、Robot Vacuum Cleaner - Codeforces
滲透測試 ( 1 ) --- 必備 工具、導航
Radar equipment (greedy)
Truck History
浏览器打印边距,默认/无边距,占满1页A4
Openwrt build Hello ipk
Auto. Getting started with JS
C language is the watershed between low-level and high-level
MySQL grants the user the operation permission of the specified content
AcWing:第58场周赛
Auto.js入门
渗透测试 2 --- XSS、CSRF、文件上传、文件包含、反序列化漏洞
读取和保存zarr文件
b站 實時彈幕和曆史彈幕 Protobuf 格式解析
Flask框架配置loguru日志库
Write web games in C language
Pytorch extract skeleton (differentiable)