はじめに
ちょっと休憩程度に68、69をします(簡単っぽそうだった)
68 NTL_1_A - 素因数分解
問題はこちらです！
問題文↓
Nが与えられるので、素因数分解してください
出力形式は`${N}:`に続き各素因数の前に空白(スペース)を入れてください
例えば、12: 2 2 3などです
素因数分解の関数を入れてたら簡単に出来ます
コードはこんな感じです
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rep1(i, n) for (ll i = 1; i <= (n); ++i) #define rrep(i, n) for (ll i = n; i > 0; --i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; using ld = long double; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; ll smallMOD = 998244353; ll bigMOD = 1000000007; int dx[] = {1, 0, -1, 0, 1, -1, -1, 1}; int dy[] = {0, 1, 0, -1, 1, 1, -1, -1}; void prime_factorize(ll N, vector<pair<ll, ll>> &res) { for (ll p = 2; p * p <= N; ++p) { if (N % p != 0) continue; int e = 0; while (N % p == 0) { ++e; N /= p; } res.emplace_back(p, e); } if (N != 1) { res.emplace_back(N, 1); } } int main() { ll n; cin >> n; vector<pair<ll, ll>> res; prime_factorize(n, res); cout << n << ":"; rep(i, res.size()) { rep(j, res[i].second) { cout << " " << res[i].first; } } cout << endl; return 0; }
ライブラリ入れているので簡単でしたー
69 AtCoder Beginner Contest 084 D - 2017-like Number
問題はこちらです！
問題文↓
Nも(N+1)/2も素数を満たす奇数Nを2017に似た数とします 区間L,Rにおいて、2017に似た数はいくつありますか？
制約が1e5までなので、そこまでの2017に似た数を全探索します
次に、区間の和として捉えて、累積和を作成することで、O(N+Q)で解くことが出来ました
コードはこんな感じです
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rep1(i, n) for (ll i = 1; i <= (n); ++i) #define rrep(i, n) for (ll i = n; i > 0; --i) #define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define yesNo(b) ((b) ? "Yes" : "No") using ll = long long; using ull = unsigned long long; using ld = long double; string alphabet = "abcdefghijklmnopqrstuvwxyz"; string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const double pi = 3.141592653589793; ll smallMOD = 998244353; ll bigMOD = 1000000007; int dx[] = {1, 0, -1, 0, 1, -1, -1, 1}; int dy[] = {0, 1, 0, -1, 1, 1, -1, -1}; bool isPrime(ll n) { if (n == 1) return false; for (ll i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; } int main() { // 先に2017に似た数を作る. map<ll, bool> like2017; rep(i, 1e5) { if (isPrime(i + 1) && (i + 2) % 2 == 0 && isPrime((i + 2) / 2)) { like2017[i + 1] = true; } } // 区間の個数の累積和を作る. vector<ll> like2017sum(1e5 + 1, 0); rep(i, 1e5) { like2017sum[i + 1] = like2017sum[i] + like2017[i + 1]; } // クエリを処理する. ll q; cin >> q; rep(i, q) { ll l, r; cin >> l >> r; cout << like2017sum[r] - like2017sum[l - 1] << endl; } return 0; }
最後に
次こそは区間DPをしたい
無理だったらべき乗の計算に逃げる
