Islamic Universtiy,Bangladesh TopH 9th CPU CSE Programming Contest C. Birth Day Gift Solution

 

 Problem Link :  https://toph.co/arena?practice=647629a9d47a320767bffe27#!/p/6474e251d47a320767bfdfce

Solution in C++:

1. /// Author : AH_Tonmoy
2. #include <bits/stdc++.h>
3. using namespace std;
4. const int mx = 2e7 + 3;
5. using ll = long long;
6. ll vis[mx], prime[mx], k;
7. void sieve() {
8. for (int i = 3; i <= mx; i += 2) {
9. if (vis[i] == 0) {
10. for (int j = 2 * i; j <= mx; j += i) {
11. vis[j] = 1;
12. }
13. }
14. }
15. vis[0] = vis[1] = 1;
16. prime[0] = 2;
17. k = 1;
18. for (int i = 3; i <= mx; i += 2) {
19. if (!vis[i]) {
20. prime[k] = i;
21. k++;
22. }
23. }
24. }
25. ll NOD(ll n) {
26. int ans = 1;
27. for (int i = 0; i < k and prime[i] * prime[i] <= n; i++) {
28. if (n % prime[i] == 0) {
29. int cnt = 0;
30. while (n % prime[i] == 0) {
31. n /= prime[i];
32. cnt++;
33. }
34. cnt++;
35. ans *= cnt;
36. }
37. }
38. if (n != 1) {
39. ans *= 2;
40. }
41. return ans;
42. }
43. int32_t main() {
44. ios_base::sync_with_stdio(0);
45. cin.tie(0);
46. sieve();
47. ll t;
48. cin >> t;
49. while (t--) {
50. ll n;
51. cin >> n;
52. cout << NOD(n) << '\n';
53. }
54. return 0;
55. }