Submission #1080689
Source Code Expand
#include <algorithm> #include <cassert> #include <cfloat> #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <deque> #include <iomanip> #include <iostream> #include <limits> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <tuple> #include <vector> #define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i)) #define rep(i,n) FOR(i,0,n) #define pb push_back #define all(v) begin(v), end(v) #define debug(x) cerr<< #x <<": "<<x<<endl #define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<vector<int> > vvi; typedef vector<ll> vll; typedef vector<vector<ll> > vvll; template<class T> using vv=vector<vector< T > >; int mod = 1e9 + 7; struct Prime { int max_check; int max_prime; int prime_number; vector<int> primes; map<int, int> prime_id; Prime() {}; Prime(int m) { initialize(m); }; void initialize(int m) { sieve(m); prime_number = (int)primes.size(); max_check = m; } void sieve(int m) { max_prime = 2; deque<bool> is_prime(m+1, true); is_prime[0] = is_prime[1] = false; int i; for (i = 2; i <= m; ++i) { if (!is_prime[i]) { continue; } if (i * i > m) { break; } for (int j = i*2; j <= m; j += i) { is_prime[j] = false; } prime_id[i] = (int)primes.size(); primes.push_back(i); max_prime = i; } for (int j = i; j <= m; ++j) { if (!is_prime[j]) { continue; } prime_id[j] = (int)primes.size(); primes.push_back(j); max_prime = j; } } map<int, int> prime_factor(ll x) { map<int, int> ret; if ((ll)max_check * (ll)max_check < x) { return ret; } for (int i = 0; i < prime_number; ++i) { while (x % primes[i] == 0) { x /= primes[i]; ret[primes[i]] += 1; } } if (x != 1) { ret[x] += 1; } return ret; } }; int main() { ll a, b; scanf("%lld %lld", &a, &b); Prime pr(31623); map<int, int> factors; for (ll c = b+1; c <= a; ++c) { auto tmp = pr.prime_factor(c); for (auto e : tmp) { factors[e.first] += e.second; } } ll ans = 1; for (auto e : factors) { ans = ans * (e.second + 1) % mod; } printf("%lld\n", ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - 約数かつ倍数 |
User | tspcx |
Language | C++11 (GCC 4.8.1) |
Score | 100 |
Code Size | 2601 Byte |
Status | AC |
Exec Time | 26 ms |
Memory | 1264 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:105:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%lld %lld", &a, &b); ^
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 5 / 5 | 35 / 35 | 60 / 60 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt |
Subtask1 | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt |
Subtask2 | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt |
Subtask3 | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt, subtask3_31.txt, subtask3_32.txt, subtask3_33.txt, subtask3_34.txt, subtask3_35.txt, subtask3_36.txt, subtask3_37.txt, subtask3_38.txt, subtask3_39.txt, subtask3_40.txt, subtask3_41.txt, subtask3_42.txt, subtask3_43.txt, subtask3_44.txt, subtask3_45.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample_01.txt | AC | 20 ms | 1176 KB |
subtask0_sample_02.txt | AC | 21 ms | 1172 KB |
subtask0_sample_03.txt | AC | 24 ms | 1172 KB |
subtask0_sample_04.txt | AC | 22 ms | 1172 KB |
subtask1_01.txt | AC | 21 ms | 1172 KB |
subtask1_02.txt | AC | 21 ms | 1088 KB |
subtask1_03.txt | AC | 20 ms | 1164 KB |
subtask1_04.txt | AC | 21 ms | 1176 KB |
subtask1_05.txt | AC | 21 ms | 1168 KB |
subtask1_06.txt | AC | 21 ms | 1176 KB |
subtask1_07.txt | AC | 21 ms | 1120 KB |
subtask1_08.txt | AC | 21 ms | 1176 KB |
subtask1_09.txt | AC | 20 ms | 1172 KB |
subtask1_10.txt | AC | 21 ms | 1172 KB |
subtask1_11.txt | AC | 19 ms | 1176 KB |
subtask1_12.txt | AC | 21 ms | 1172 KB |
subtask1_13.txt | AC | 21 ms | 1168 KB |
subtask1_14.txt | AC | 20 ms | 1264 KB |
subtask1_15.txt | AC | 21 ms | 1172 KB |
subtask2_16.txt | AC | 24 ms | 1176 KB |
subtask2_17.txt | AC | 23 ms | 1172 KB |
subtask2_18.txt | AC | 20 ms | 1160 KB |
subtask2_19.txt | AC | 23 ms | 1168 KB |
subtask2_20.txt | AC | 21 ms | 1168 KB |
subtask2_21.txt | AC | 25 ms | 1172 KB |
subtask2_22.txt | AC | 20 ms | 1168 KB |
subtask2_23.txt | AC | 23 ms | 1220 KB |
subtask2_24.txt | AC | 22 ms | 1176 KB |
subtask2_25.txt | AC | 25 ms | 1176 KB |
subtask2_26.txt | AC | 22 ms | 1172 KB |
subtask2_27.txt | AC | 26 ms | 1176 KB |
subtask2_28.txt | AC | 20 ms | 1108 KB |
subtask2_29.txt | AC | 23 ms | 1172 KB |
subtask2_30.txt | AC | 21 ms | 1176 KB |
subtask3_31.txt | AC | 23 ms | 1172 KB |
subtask3_32.txt | AC | 21 ms | 1168 KB |
subtask3_33.txt | AC | 25 ms | 1068 KB |
subtask3_34.txt | AC | 21 ms | 1172 KB |
subtask3_35.txt | AC | 24 ms | 1172 KB |
subtask3_36.txt | AC | 21 ms | 1172 KB |
subtask3_37.txt | AC | 26 ms | 1176 KB |
subtask3_38.txt | AC | 23 ms | 1172 KB |
subtask3_39.txt | AC | 26 ms | 1084 KB |
subtask3_40.txt | AC | 22 ms | 1168 KB |
subtask3_41.txt | AC | 24 ms | 1164 KB |
subtask3_42.txt | AC | 24 ms | 1172 KB |
subtask3_43.txt | AC | 25 ms | 1168 KB |
subtask3_44.txt | AC | 22 ms | 1132 KB |
subtask3_45.txt | AC | 24 ms | 1172 KB |