Advertisement
momo2345

NumberOfDivisors

May 4th, 2021
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.23 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define suni ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  4. #define ll long long
  5. #define pb push_back
  6. #define endl "\n"
  7. const int mx = 1e6+123;
  8. vector<int>primefactorization[mx];
  9. bitset<mx> is_prime;
  10. vector<int> prime;
  11.  
  12. void primegen ( int n )
  13. {
  14. n += 100;
  15. for ( int i = 3; i <= n; i += 2 ) is_prime[i] = 1;
  16.  
  17. int sq = sqrt ( n );
  18. for ( int i = 3; i <= sq; i += 2 ) {
  19. if ( is_prime[i] == 1 ) {
  20. for ( int j = i*i; j <= n; j += ( i + i ) ) {
  21. is_prime[j] = 0;
  22. }
  23. }
  24. }
  25.  
  26. is_prime[2] = 1;
  27. prime.push_back (2);
  28.  
  29. for ( int i = 3; i <= n; i += 2 ) {
  30. if ( is_prime[i] == 1 ) prime.push_back ( i );
  31. }
  32. }
  33. ll NOD(ll l)
  34. {
  35. int ret=1,cnt=1;
  36. for(auto p: prime)
  37. {
  38. if(1LL*p*p >l) break;
  39. if(l%p==0)
  40. {
  41. cnt=1;
  42. while(l%p==0)
  43. {
  44. cnt++;
  45. l/=p;
  46. }
  47. ret*=cnt;
  48. }
  49. }
  50. if(l>1) ret*=2;
  51. return ret;
  52. }
  53. int main()
  54. {
  55. suni;
  56. primegen(1e6);
  57. int t; cin>>t;
  58. while(t--){
  59. ll n;
  60. cin>>n;
  61. cout<<NOD(n)<<endl;
  62. }
  63. return 0;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement