fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/tree_policy.hpp>
  3. #include <ext/pb_ds/assoc_container.hpp> 
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update > pbds;
  9. // find_by_order, order_by_key
  10.  
  11. #define sp << " " << 
  12. #define ll long long
  13. #define ld long double
  14. #define pb push_back
  15. #define F first
  16. #define S second
  17. #define PI 3.1415926535897932384626
  18.  
  19. #define all(x) x.begin(), x.end()
  20. #define rall(x) x.rbegin(), x.rend()
  21. #define sortall(x) sort(all(x))
  22. #define sortrall(x) sort(rall(x))
  23.  
  24. #define printv(v) for(auto x : v) cout << x << " "; cout << "\n"
  25. #define printm(m) for(auto x : m) cout << x.F sp x.S << "\n"
  26.  
  27. #define make_unique(x) sortall(x); (x).resize(unique(all(x)) - (x).begin())
  28. #define numtobin(n) bitset<32>(n).to_string() 
  29. #define bintoint(bin_str) stoi(bin_str, nullptr, 2)
  30.  
  31. struct custom_hash {
  32.     static uint64_t splitmix64(uint64_t x) {
  33.         x += 0x9e3779b97f4a7c15;
  34.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  35.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  36.         return x ^ (x >> 31);
  37.     }
  38.  
  39.     size_t operator()(uint64_t x) const {
  40.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  41.         return splitmix64(x + FIXED_RANDOM);
  42.     }
  43. };
  44.  
  45. template<typename T1, typename T2>
  46. using safe_map = unordered_map<T1, T2, custom_hash>;
  47.  
  48. template<typename T>
  49. using safe_set = unordered_set<T, custom_hash>;
  50.  
  51. template<typename T>
  52. void debug(T x) { cerr << x << endl; }
  53.  
  54. template<typename T, typename... Args>
  55. void debug(T x, Args... args) { cerr << x << " "; debug(args...); }
  56.  
  57. void fastIO() {
  58.     ios_base::sync_with_stdio(false);
  59.     cin.tie(NULL); cout.tie(NULL);
  60. }
  61.  
  62. void fraction() {
  63.     cout.unsetf(ios::floatfield); 
  64.     cout.precision(10); 
  65.     cout.setf(ios::fixed,ios::floatfield);
  66. }
  67.  
  68. void yn(bool res, bool cap = true) {
  69.     vector<string> s = {"Yes", "YES", "No", "NO"};
  70.     cout << ((res) ? s[0 + cap] : s[2 + cap]) << "\n";
  71. }
  72.  
  73. void chmin(ll &x, ll y) { x = min(x, y); }
  74. void chmax(ll &x, ll y) { x = max(x, y); }
  75.  
  76. inline ll nxt() { ll x; cin >> x; return x;}
  77. inline ld nxtD() { ld x; cin >> x; return x;}
  78. inline string nxtStr() { string x; cin >> x; return x;}
  79.  
  80. const int mod = 998'244'353;
  81. const int INF = 1e9;
  82. const ll LINF = 1e18;
  83.  
  84. const int mx = 3e5+123;
  85. vector<vector<ll>> primes;
  86.  
  87. void primeGen(){
  88.     primes.resize(mx);
  89.     for(int i = 2; i < mx; i++) {
  90.         if(!primes[i].size()) {
  91.             for(int j = i; j < mx; j+=i)
  92.                 primes[j].pb(i);
  93.         }
  94.     }
  95. }
  96.  
  97. const int N = 1e6 + 9;
  98.  
  99. int f[N], inv[N], finv[N];
  100. void prec() {
  101.     f[0] = 1;
  102.     for (int i = 1; i < N; i++) f[i] = 1LL * i * f[i - 1] % mod;
  103.     inv[1] = 1;
  104.     for (int i = 2; i < N; i++ ) {
  105.         inv[i] = (-(1LL * mod / i) * inv[mod % i] ) % mod;
  106.         inv[i] = (inv[i] + mod) % mod;
  107.     }
  108.     finv[0] = 1;
  109.     for (int i = 1; i < N; i++) finv[i] = 1LL * inv[i] * finv[i - 1] % mod;
  110. }
  111.  
  112. int ncr(int n, int r) {
  113.     if (n < r || n < 0 || r < 0) return 0;
  114.     return 1LL * f[n] * finv[n - r] % mod * finv[r] % mod;
  115. }
  116.  
  117. void proc(){
  118.     primeGen();
  119.     prec();
  120. }
  121.  
  122. void solve() {
  123.     int n, k; cin >> n >> k;
  124.     safe_map<ll, ll> mp;
  125.     for(int i = 0; i < n; i++) {
  126.         int x; cin >> x;
  127.         for(auto p : primes[x])
  128.             mp[p]++;
  129.     }
  130.  
  131.  
  132.     ll ans = 0, res = 0;
  133.     for(auto [p, c] : mp) { 
  134.         res = (ncr(n, k) - ncr(n-c, k) + mod) % mod;
  135.         res = (res * p) % mod;
  136.         ans = (ans + res) % mod;
  137.     }
  138.  
  139.     cout << ans << "\n";
  140. }
  141.  
  142. int main() {
  143.     fastIO(); 
  144.     proc();
  145.  
  146.     int tc = 1;
  147.     tc = nxt();
  148.     for (int t = 1; t <= tc; t++) {
  149.         // cout << "Case " << t << ": ";
  150.         solve();
  151.     }
  152. }
  153.  
  154.  
Success #stdin #stdout 0.17s 35384KB
comments (?)
stdin
copy 
3
4 2
2 1 3 4
3 3
2 2 2
1 1
1
stdout
copy 
19
2
0
https://ideone.com/qhPc1m
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!