fork(1) download
copy 
  1. /// You just can't beat the person who never gives up
  2. /// ICPC next year
  3.  
  4. #include<bits/stdc++.h>
  5. using namespace std ;
  6.  
  7. const int N = 1e5+5 ;
  8.  
  9. int t ,n ,k ,nxt_prime[N] ;
  10. int spf[N];
  11. vector<pair<int,int>> f ;
  12. void sieve(){
  13.     for(int i=1;i<N;++i) spf[i]=i;
  14.     for(int i=2;i*i<N;++i)if(spf[i]==i){
  15.         for(int j=i*i;j<N;j+=i)if(spf[j]==j)spf[j]=i;
  16.     }
  17. }
  18. vector<int> factorize(int x){
  19.     vector<int> ret;
  20.     while(x!=1){
  21.         ret.push_back(spf[x]);
  22.         x/=spf[x];
  23.     }
  24.     sort(ret.begin(),ret.end());
  25.     return ret ;
  26. }
  27. int cnt[N] ;
  28. long long solve3(int val,int l,int r){
  29.     if(val>n) return 0;
  30.     if(1ll*val*l>n) return 1;
  31.     if(l>r) return 1;
  32.     long long ret = solve3(val,nxt_prime[l],r);
  33.     if(cnt[l]) return ret ;
  34.     return ret + solve3(val*l,l,r);
  35. }
  36. long long solve2(int val,int r,int i,int rem){
  37.     if(rem==0) return solve3(val,2,r);
  38.     if(i==f.size()) return 0;
  39.     if(!f[i].second) return solve2(val,r,i+1,rem) ;
  40.     --f[i].second ;
  41.     --cnt[f[i].first] ;
  42.     long long ret = solve2(val*f[i].first,f[i].first,i,rem-1);
  43.     ++f[i].second ;
  44.     ++cnt[f[i].first] ;
  45.     ret += solve2(val,r,i+1,rem);
  46.     return ret ;
  47. }
  48. long long solve(int x){
  49.     vector<int> fac = factorize(x) ;
  50.     if(fac.size()<k+k) return 0;
  51.     int cur = 1 ;
  52.     for(int i=0;i<k;++i) cur *= fac[i] ;
  53.     reverse(fac.begin(),fac.end());
  54.     for(int i=0;i<k;++i) fac.pop_back();
  55.     reverse(fac.begin(),fac.end());
  56.     f.clear() ;
  57.     for(int i:fac){
  58.         if(!f.size() || i!=f.back().first) f.push_back({i,1});
  59.         else ++f.back().second ;
  60.     }
  61.     reverse(f.begin(),f.end());
  62.     for(auto go:f) cnt[go.first] = go.second ;
  63.     long long ret =  solve2(cur,n,0,k);
  64.     for(auto go:f) cnt[go.first] = 0 ;
  65.     return ret ;
  66. }
  67. int main(){
  68.     sieve();
  69.     int nxt = N-1 ;
  70.     for(int i=N-1;i>=0;--i){
  71.         if(i+1<N) nxt_prime[i] = nxt ;
  72.         if(spf[i]==i) nxt = i ;
  73.     }
  74.  
  75.     scanf("%d",&t);
  76.     while(t--){
  77.         scanf("%d%d",&n,&k);
  78.         if(k>8){
  79.             puts("0") ;
  80.             continue ;
  81.         }
  82.         long long ans = 0 ;
  83.         for(int i=1;i<=n;++i) ans += solve(i) ;
  84.         printf("%lld\n",ans);
  85.     }
  86.  
  87.     return 0;
  88. }
  89.  
Success #stdin #stdout 0s 4944KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/61h70N
language:
C++14 (gcc 8.3)
created:
3 years 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!