CodeForces 893B Beautiful Divisors"/>
CodeForces 893B Beautiful Divisors
Description:
Recently Luba learned about a special kind of numbers that she calls beautiful numbers. The number is called beautiful iff its binary representation consists of k + 1 consecutive ones, and then k consecutive zeroes.
Some examples of beautiful numbers:
- 12 (110);
- 1102 (610);
- 11110002 (12010);
- 1111100002 (49610).
More formally, the number is beautiful iff there exists some positive integer k such that the number is equal to (2k - 1) * (2k - 1).
Luba has got an integer number n, and she wants to find its greatest beautiful divisor. Help her to find it!
The only line of input contains one number n (1 ≤ n ≤ 105) — the number Luba has got.
Output one number — the greatest beautiful divisor of Luba's number. It is obvious that the answer always exists.
3Output
1Input
992Output
496
题目大意:
给定一个n,求小于等于n的最大的漂亮数字。漂亮数字的定义是二进制下前k个数字都为1, 后k + 1个数字都为0的十进制数字。
解题思路:
因为要求最大的, 我们只要从小于等于n的漂亮数字中从后往前枚举看是否能被整除即可。
代码:
#include <iostream>
#include <sstream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <utility>
#include <string>
#include <cmath>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
using namespace std;
/*
*ios::sync_with_stdio(false);
*/
typedef long long ll;
typedef unsigned long long ull;
const int dir[5][2] = {0, 1, 0, -1, 1, 0, -1, 0, 0, 0};
const ll ll_inf = 0x7fffffff;
const int inf = 0x3f3f3f;
const int mod = (int)1e9 + 7;
const int Max = (int) 1e5 + 7;
int ans, cur;
int main() {
int n;
ans = 1, cur = 1;
scanf("%d", &n);
while (ans <= n) {
cur++;
int x = 0;
for (int i = cur - 1; i <= cur + cur - 2; ++i) {
x += (1 << i);
}
ans = x;
}
for (int i = cur; i >= 1; --i) {
int temp = 0;
for (int j = i - 1; j <= i + i - 2; ++j) {
temp += (1 << j);
}
if (n >= temp && n % temp == 0) {
printf("%d\n", temp);
return 0;
}
}
}
更多推荐
CodeForces 893B Beautiful Divisors
发布评论