Inclusion Exclusion

I am sure that most of you have heard of the inclusion exclusion principle.  If not then I suggest that you either head over to Google or Wikipedia.  It is a really useful technique with many applications; even to this day I am still discovering new ways in which it can be used.

In this post I will outline a partial solution to the following problem located on SPOJ, PGCD.

The first thing you should notice is that the answer to (a,b) will be the same as the solution to (b,a).  This is because of the symmetry of the operation, thus suppose that .

Suppose that there are columns in our gcd table.  We will find how many primes there are in each column.  Suppose that there are rows, and we are looking at column , where are distinct primes.  I’m not going to consider the case where a prime factor is repeated, though I have a feeling that the solution below should still work.

First we find how many multiples there are of each prime between .  This is just

But what about the multiples of say, ?  Well they were counted twice, and their entry in the table is not going to be a prime (you can easily convince yourself of this fact).  So we just subtract them out twice, leaving our answer as

Now what about the divisors of with exactly 3 prime factors?  Their multiples have been removed too many times, thus we need to add them back.  If we continue this way we see that we will be using inclusion exclusion.

So to solve this we can use the following code.

#include bitset
#include vector

int answer=0;
bitset PIE;
for(int i=2 to n;++i)
{
	vector prime_factors=factor(i);
	int r=prime_factors.size();
	for(int cnt=1 to 2^r - 1;++cnt)
	{
		PIE=cnt;//express cnt in base 2 and store in PIE
		int ones=PIE.count();//the number of 1s in our bit string
		int p=1;
		for(int j=0 to prime_factors.size() -1;++j)
			if(PIE[j])
				p*=prime_factors[j];
		if(ones&1)//there are an odd number of 1s
			answer+=(ones*(m/p));
		else//there are an even number of 1s
			answer-=(ones*(m/p));
	}
}

This isn’t totally legal code because I had to paste it into HTML so the less than and greater than signs disappear and I don’t want to waste the time to fix it (even though I know how to).
For those of you that don’t know the bitset is just a string of 1s and 0s. When I did PIE=cnt I basically set it so that the bit string was equal to the base 2 representation of cnt. Using this method we can get all possible combinations of the prime factors.
The code can easily be converted to Java since I think it too has something similar to a bitset. If your language of choice doesn’t have a bit set, no need to worry. You can just get the base 2 representation on your own (it’s not that hard, trust me).
WARNING: This approach will only be feasible if each number doesn’t have too many prime factors. Not the case with the problem on SPOJ since each number can be decomposed into the product of at most 23 primes, and at most 9 distinct primes. So I’m not sure if the time limit will allow you use this method, I haven’t tried, but please let me know if you do.

Included Files

Do you ever wonder where the files you include in your C/C++ programs are located, and how the linker finds them?  Well on a Linux system (unless you have changed things) they are located at /usr/include and /usr/include/c++.  If you go you can see the list of files you can #include in your program.  Additionally, you can view the source code, if you are the kind of person (and I have a feeling that you are) that finds these things interesting.

Thoughts on my Nexus One

Well I’m not the first person to buy a Nexus One in America, but I’m one of the last to do so.  As a responsible consumer it is my duty to share my experiences with you readers.  I’ve had the phone for a little more than a week and thus think I know how I will be using it for the most part. Before I start I would like to mention that the biggest problem I have with the phone is my phone number.  This has nothing to do with Google/HTC, but rather T-mobile, so this little issue won’t be making it into the review.

At first I thought about just having this review be another pros/cons list.  But when I started there were many things that fell into both categories.  So I realized it would be easier, and a little more organized if I just commented on each aspect one at a time.

OPERATING SYSTEM: This is a big plus.  The Nexus One is the only phone currently on the market running a legitimate version of Android 2.2.  Although the phone ships with version 2.1 it starts to download the update soon after activation.  There is a noticeable speed difference between the two versions.  Also the ability to use the phone as a wireless hot-spot is wonderful (in my case it doesn’t cost me any extra for this feature).  The added flash support doesn’t hurt either.  For more information about the update just look on any tech website/blog, or even do a quick search for ‘Android 2.2′.

USER INTERFACE: The screen is usually quick to react to all of touch commands.  When this isn’t the case, it is almost always do to an application freezing, something the phone can’t take all the blame for (I’m looking at you app developer).  The phone comes with 5 screens for you to place icons, for me this is a bit much since I only really use 4.  For those of you that are used to using the HTC Sense UI that comes with 7 screens (or so I have read) this might feel like a downgrade.  Another thing that matters is screen brightness.  You are able to choose between 3 screen brightness levels.  Obviously the brighter the screen the more strain you will be putting on the battery.  I find that the dimmest level is more than good enough when you are inside and the second level (out of 3) is fine when you are in obstructed sunlight.  I don’t know how well the screen manages when you are in direct sunlight but my guess is that even on the brightest setting you will still need to cup your hands over the phone if you want to see more than just large icons (you know…things like text).

KEYBOARD: You should know that I would have preferred the Nexus One to have had a physical keyboard as an option instead of only the on-screen keyboard that is provided.  Since there isn’t much I can do about this (though I think there might be ways to connect to an external keyboard, probably through bluetooth is my guess) I have gotten used to the set up.  If you ever need to type something that is longer than 2 words I suggest that you use the keyboard in landscape mode.  Otherwise your thumbs will accidentally hit wrong keys and increase the number of typos.  The only problem with typing in the landscape mode is that the keyboard takes up most of the screen.  Thus if you need to enter text into more than one area you will have to close the keyboard after each entry.  When using the portrait version you don’t have this problem, but as mentioned before you are more typo prone.

SOFT KEYS and TRACKBALL: I refer to the four keys located right above the track ball as the soft keys.  The trackball is quite useful when the area you need to click is too small for you to accurately do so by touch.  I would prefer that instead of a physical ball it was laser operated, similar to the Droid Incredible.  However, both versions do have their downfalls.  If something goes wrong with the laster/hardware or you damage the physical trackball then you are just SOL in both cases.  As for the soft keys they work well most of the time.  The only time I have a problem is when the phone is parallel to the ground.  When this happens you have to press a button repeatedly for it to perform is designated action.  Sometimes even that isn’t enough if you aren’t pushing the button in the right place (near the top close to the screen edge).  Some other reviews claim that the back button is confusing, but I find it rather intuitive; it will always take you to the previously viewed screen, so this isn’t a problem unless you have horrible short term memory.

BATTERY: Depending on use I can get anywhere between half a day and two days from a full battery.  Removing the batter is rather simple…once you are able to remove the back of the phone, which isn’t quite as simple.

OVERALL: I’ll keep this short, 4/5.  The reason for a 4 and not anything higher is because of the keyboard, screen in the sun, and  the fact that there are more “advanced” phones out there.  Though the Nexus One is “old”, it is by no means irrelevant.  It is still the phone that the Google developers use to do testing (I’m sure it’s not the only phone but it is certainly one they make sure their product works on.  Which is part of the reason this is the only phone running Android 2.2).