Question Name:Power of Twos

#include<bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long ll;
#define se second
#define fi first
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define itr(it,l,x) for(auto it=l[x].begin();it!=l[x].end();it++)
#define go(it,mp) for(auto it=mp.begin();it!=mp.end();it++)
ll domod(ll m,ll k)
{if(m>k)return m-k;}
#define f(i,a,b) for(i=a;i<b;i++)
template <typename T>      /*use iff inputs >0*/
inline void in(T &a) {
	register T c;
	a = 0;
	do c = getchar_unlocked(); while(c < '0');
	do {
		a = (a << 1) + (a << 3) + c - '0';
		c = getchar_unlocked();
	} while (c >= '0');
}
ll read () {      /*use for all cases but is slightly slower than above*/
	bool minus = false;
	ll result = 0;
	char ch;
	ch = getchar();
	while (true) {
		if (ch == '-') break;
		if (ch >= '0' && ch <= '9') break;
		ch = getchar();
	}
	if (ch == '-') minus = true; else result = ch-'0';
	while (true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = result*10 + (ch - '0');
	}
	if (minus)
		return -result;
	else
		return result;
}
template <typename T>
inline void pr(T a) {
	char s[11];
	T t = -1;
	do {
		s[++t] = a % 10 + '0';
		a /= 10;
	} while (a > 0);
	while (t >= 0) putchar_unlocked(s[t--]);
	putchar_unlocked('\n');
}
int main()
{
    ll i,q,n,j;
    ll dp[1000001]={0};
    for(i=1;i<=1000000;i++)
    for(j=2*i;j<=1000000;j+=i)
    dp[j]++;
    f(i,2,1000001)
    dp[i]+=dp[i-1];
    cin>>q;
    while(q--)
    {
        cin>>n;
        cout<<dp[n]<<endl;
    }
}
  • Problem Description
    Little Jhool is friend with the magical creature from Koi Mil Gaya as we all know, called Jaadu. Now, Jhool is learning Mathematics from Jaadu; he wants to know about the Mathematics of the other planet, too.

    In Jaadu’s planet, the sequence of powers of two are called the: The JP. (Jaadu power!) That is, 2^1,2^2,2^3….2^1000000. 10,00,000 being the limit known to the people on Jaadu’s planet. Also, Jhool is smart so he notices that this particular sequence starts from index 1 and NOT 0. Now since Jhool thinks that he’s understood the sequence well, already so he challenges Jaadu.

    Jaadu gives him a number, denoted by N, and asks Jhool to find the number of pairs (i,j) such that (JP[i]-1) divides (JP[j]-1) and 1<=i<j<=N. Jhool is stunned by this difficult question. And needs your help!

    Input:
    First line contains number of test cases T. Each test cases contains single integer N.

    Output

    For each test case print total numbers of pairs (i,j) such that 1<= i<j<=N and JP[i]-1 is divisors of JP[j]-1.

    Constraints: 

    1<=T<=10000 
    1<=N<=1000000
  • Test Case 1
    Input (stdin)3
    1 2 3
    Expected Output0
    1
    2
  • Test Case 2
    Input (stdin)20
    100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120
    Expected Output382
    383
    390
    391
    398
    405
    408
    409
    420
    421
    428
    431
    440
    441
    448
    451
    456
    461
    464
    467

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro