結果
問題 | No.546 オンリー・ワン |
ユーザー | bal4u |
提出日時 | 2019-04-20 19:38:56 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 1 ms / 2,000 ms |
コード長 | 1,248 bytes |
コンパイル時間 | 295 ms |
コンパイル使用メモリ | 30,976 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-01 21:06:14 |
合計ジャッジ時間 | 907 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 7 |
コンパイルメッセージ
main.c: In function 'in': main.c:7:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration] 7 | #define gc() getchar_unlocked() | ^~~~~~~~~~~~~~~~ main.c:13:24: note: in expansion of macro 'gc' 13 | int n = 0, c = gc(); | ^~
ソースコード
// yukicoder: No.546 オンリー・ワン// 2019.4.20 bal4u#include <stdio.h>#if 1#define gc() getchar_unlocked()#else#define gc() getchar()#endifint in() // 非負整数の入力{int n = 0, c = gc();do n = 10 * n + (c & 0xf), c = gc(); while (c >= '0');return n;}int gcd(int a, int b){int r;while (b != 0) r = a % b, a = b, b = r;return a;}long long lcm(int a, int b){return (long long)a/gcd(a, b)*b;}int N, L, H;int c[12];int ans;/* 2^16までのビット数を数える */int bitcount(int x){x = ((x & 0xAAAAAA) >> 1) + (x & 0x555555);x = ((x & 0xCCCCCC) >> 2) + (x & 0x333333);x = ((x & 0xF0F0F0) >> 4) + (x & 0x0F0F0F);return ((x & 0x00FF00) >> 8) + (x & 0xFF00FF);}int main(){int i, j, k, t, lim;long long g;N = in(), L = in()-1, H = in();ans = 0;for (i = 0; i < N; i++) {c[i] = in();ans += (H/c[i] - L/c[i]);}if (N >= 2) {lim = 1<<N;for (i = 1; i < lim; i++) {if ((k = bitcount(i)) == 1) continue;g = 1;for (j = 0; j < N; j++) if ((i >> j) & 1) {g = lcm((int)g, c[j]);if (g > H) break;}if (g <= H) {t = k * (H/(int)g - L/(int)g);if (k & 1) ans += t; else ans -= t;}}}printf("%d\n", ans);return 0;}