結果
問題 | No.152 貯金箱の消失 |
ユーザー |
|
提出日時 | 2014-12-18 19:17:23 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,522 bytes |
コンパイル時間 | 1,670 ms |
コンパイル使用メモリ | 159,876 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-12 01:09:17 |
合計ジャッジ時間 | 1,803 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 12 |
ソースコード
#include <bits/stdc++.h>using namespace std;const int r_max = 2500;int min_p[r_max + 10], ps[r_max + 10];int use_p[20];int gcd(int a, int b){if(b == 0)return a;return gcd(b, a % b);}int lcm(int a, int b){return a / gcd(a, b) * b;}int max_m(int L, int n){int m = (int)((sqrt(2 * L + 4 * n * n) - 2 * n) / 4) - 2;m = max(n + 1, m);while(8 * m * (n + m) <= L)++m;--m;return m;}int solve(int size, int upper){if(use_p[0] != 2)upper /= 2;int res = upper;for(int mask=1;mask<1<<size;mask++){int L = 1;int cnt = 0;for(int i=0;i<size;i++)if((mask >> i) & 1){L = lcm(L, use_p[i]);++cnt;}if(cnt % 2 == 1){res -= upper / L;} else {res += upper / L;}}return res;}int solve(int L){int res = max_m(L, 1) / 2;for(int n=2;8*(n+1)*(2*n+1)<=L;n++){int size = 0;use_p[size++] = min_p[n];int t = n / min_p[n];while(t > 1){if(use_p[size-1] != min_p[t]){use_p[size++] = min_p[t];}t /= min_p[t];}res += solve(size, max_m(L, n)) - solve(size, n);}return (res % 1000003);}int main(){for(int n=2;n<=r_max;n++)min_p[n] = n;int ps_size = 0;for(int n=2;n<=r_max;n++){if(min_p[n] == n){ps[ps_size++] = n;}for(int i=0;i<ps_size;i++){if(ps[i] > min_p[n])break;int np = n * ps[i];if(np > r_max)break;min_p[np] = ps[i];}}int L;cin >> L;cout << solve(L) << endl;return 0;}