1的個(gè)數(shù)
時(shí)間限制：C/C++語(yǔ)言 2000MS；其他語(yǔ)言 4000MS
內(nèi)存限制：C/C++語(yǔ)言 65536KB；其他語(yǔ)言 589824KB
題目描述：
給出三個(gè)整數(shù)a谬哀，b比吭，c绽族，你需要計(jì)算數(shù)2a +2b-2c在二進(jìn)制表示下1的個(gè)數(shù)。
輸入
第一行包含三個(gè)整數(shù)a,b,c衩藤。1≤c＜b＜a≤109
輸出
輸出對(duì)應(yīng)的答案吧慢。
提示：23+22-21=10=(1010)2
樣例輸入
3 2 1
樣例輸出
2
解析
因?yàn)閍bc之間大小關(guān)系確定，2a+2b-2c=2a+(2b-2c)=2a+(2c)(2b-c-1)
又因?yàn)?c 在2進(jìn)制上表示成1...0赏表，所以2b-c-1和它相乘不影響1的個(gè)數(shù)检诗，最終解就是b-c+1匈仗，這里1是2a帶來(lái)的
京東面試題:
牛牛對(duì)整數(shù)非常感興趣。牛牛的老師給他不知了一道題：給出一個(gè)n逢慌，牛牛要輸出一個(gè)能被1到n之間(包括1和n)所有整數(shù)整除的最小的數(shù)悠轩。牛牛犯了難，希望你能編程幫他解決攻泼。
輸入一個(gè)整數(shù)n(1<=n<=100000)
輸出描述：
輸出1個(gè)整數(shù)火架，即滿足要求的最小整數(shù)，答案可能很大忙菠，請(qǐng)輸出這個(gè)整數(shù)對(duì)于987654321取模的結(jié)果距潘。
樣例輸入：
3
樣例輸出：
6
解析
一開(kāi)始想的怎么利用gcd求這n個(gè)數(shù)的最小公倍數(shù)，但是這對(duì)于取模操作很難完成只搁。方法是：先求出[1,n]的所有素?cái)?shù)音比。因?yàn)槿魏我粋€(gè)數(shù)字都可以被素因子分解，即任何一個(gè)數(shù)都能寫(xiě)成若干素?cái)?shù)的乘積氢惋。有這樣一個(gè)答案ans=1洞翩，我們從2開(kāi)始遍歷到n：若遇到素?cái)?shù)，便讓ans乘上從該素?cái)?shù)“可能是某個(gè)數(shù)因子”的最多次焰望。比如n是8骚亿，那么素?cái)?shù)2就該乘3次，別越過(guò)n即可熊赖，3乘1次来屠，因?yàn)?次會(huì)為9越過(guò)8。那么這樣乘下來(lái)震鹉，1到n的任何一個(gè)數(shù)字都會(huì)被素?cái)?shù)最小范圍的覆蓋俱笛！簡(jiǎn)單來(lái)想：因?yàn)槊總€(gè)素?cái)?shù)作為因子乘的次數(shù)都最小(不越過(guò)n)
于是有代碼
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
const ll mod = 987654321, maxN = 1e5 + 5;
int N;
bool is_prime[maxN];
void init() {
mst(is_prime, 0);
rep(i, 2, N + 1)
is_prime[i] = 1;
rep(i, 2, N + 1)
if (is_prime[i])
for (int j = i << 1; j <= N; j += i)
is_prime[j] = 0;
}
int main() {
scanf("%d", &N);
init();
ll ans = 1;
rep(i, 2, N + 1) {
if (is_prime[i]) {
ll tmp = i;
while (tmp <= N) {
ans = ans * i % mod;
tmp *= i;
}
}
}
printf("%lld\n", ans);
return 0;
}
