Advertisement
Saleh127

UVA 13245

May 7th, 2021
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.11 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  5.  
  6. ll dp[20000];
  7. #define maX 100008
  8. bool marked[maX+2];
  9. vector<ll>p;
  10. void sieve()
  11. {
  12. marked[0]=1;
  13. marked[1]=1;
  14. p.push_back(1);
  15. p.push_back(2);
  16. for(ll i=4;i<=maX;i+=2)
  17. {
  18. marked[i]=1;
  19. }
  20. for(ll i=3;i<=maX;i+=2)
  21. {
  22. if(marked[i]==0)
  23. {
  24. p.push_back(i);
  25. for(ll j=i*i; j<=maX; j+=i+i)
  26. {
  27. marked[j]=1;
  28. }
  29. }
  30. }
  31. }
  32. ll cc(ll n,ll v)
  33. {
  34. ll i,j,k,l;
  35.  
  36. dp[0]=0;
  37.  
  38. for(i=1;i<=10000;i++)
  39. {
  40. dp[i]=INT_MAX;
  41. }
  42.  
  43. for(i=0;i<n;i++)
  44. {
  45. for(j=1;j<=v;j++)
  46. {
  47. if(j>=p[i] && dp[j]>(1+dp[j-p[i]]))
  48. {
  49. dp[j]=1+dp[j-p[i]];
  50. }
  51. }
  52. }
  53. return dp[v];
  54. }
  55.  
  56. int main()
  57. {
  58. ios_base::sync_with_stdio(0);
  59. cin.tie(0);cout.tie(0);
  60.  
  61. sieve();
  62.  
  63. test
  64. {
  65. ll n,m,i,j,k,l;
  66.  
  67. cin>>n>>m;
  68. cout<<cc(n,m)<<endl;
  69. }
  70.  
  71.  
  72. return 0;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement