Spoj ODDDIV - Odd Numbers of Divisors Solution

 

Problem Link: https://www.spoj.com/problems/ODDDIV/

Solution in C++:

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define ll long long int
4. const ll N=1e5;
5. vector<ll>prime,fact[N];
6. bool vis[N];
7. ll i,j,tem;
8. void divCount(ll n)
9. {
10. ll ans=1,tem=n;
11. for(i=0;i<prime.size() && prime[i]*prime[i]<=n;i++)
12. {
13. ll cnt=0;
14. if(n%prime[i]==0)
15. {
16. while(n%prime[i]==0)
17. {
18. cnt++;
19. n/=prime[i];
20. }
21. ans=ans*(2*cnt+1);
22. }
23. }
24. if(n>1)
25. {
26. ans=ans*3;
27. }
28. fact[ans].push_back(tem*tem);
29. }
30. void sieve()
31. {
32. for(i=3; i*i<=N; i+=2)
33. {
34. if(vis[i]==0)
35. {
36. for( j=i*i; j<=N; j+=2*i)
37. {
38. vis[j]=1;
39. }
40. }
41. }
42. prime.push_back(2);
43. for(i=3; i<=N; i+=2)
44. {
45. if(vis[i]==0)
46. {
47. prime.push_back(i);
48. }
49. }
50. }
51. int main()
52. {
53. ios_base::sync_with_stdio(0);
54. cin.tie(0);
55. sieve();
56. ll n,t,i,j,cnt,ans,k,l,r;
57. for(i=1; i<=N; i++)
58. {
59. divCount(i);
60. }
61. cin>>t;
62. while(t--)
63. {
64. cin>>k>>l>>r;
65. auto high=upper_bound(fact[k].begin(),fact[k].end(),r)-fact[k].begin();
66. auto low=lower_bound(fact[k].begin(),fact[k].end(),l)-fact[k].begin();
67. cout<<high-low<<endl;
68. }
69. }