codeforces The Wall - 題解

Iahub and his friend Floyd have started painting a wall. Iahub is painting the wall red and Floyd is painting it pink. You can consider the wall being made of a very large number of bricks, numbered 1, 2, 3 and so on.

Iahub has the following scheme of painting: he skips x?-?1 consecutive bricks, then he paints the x-th one. That is, he'll paint bricks x, 2·x, 3·x and so on red. Similarly, Floyd skips y?-?1 consecutive bricks, then he paints the y-th one. Hence he'll paint bricks y, 2·y, 3·y and so on pink.

After painting the wall all day, the boys observed that some bricks are painted both red and pink. Iahub has a lucky number a and Floyd has a lucky number b. Boys wonder how many bricks numbered no less than a and no greater than b are painted both red and pink. This is exactly your task: compute and print the answer to the question.

The input will have a single line containing four integers in this order: x, y, a, b. (1?≤?x,?y?≤?1000, 1?≤?a,?b?≤?2·109,a?≤?b).

Output a single integer — the number of bricks numbered no less than a and no greater than b that are painted both red and pink.

2 3 6 18

3

這是一道簡單題，也隔了一段時間沒做簡單題目了。

這次感覺又不一樣了，可以很快就能寫出很優雅的代碼了，故此很想貼貼自己的代碼。

優雅代碼的關鍵就是要利用數學的思想去解：

本題的實質是可以轉化為求最大公倍數的的問題，然後利用Inclusion-exclusion（包含和不包含）的原則，計算有多少個數能被a除盡這個公倍數，有多少個數能被b除盡這個公倍數，然後相減就得到最終答案了。

#include 
using namespace std;

int TheWallGCD(int a, int b)
{
	while (b)
	{
		int t = b;
		b = a % b;
		a = t;
	}
	return a;
}

void TheWall340A()
{
	int x, y, a, b;
	scanf("%d %d %d %d", &x, &y, &a, &b);
	
	int r = TheWallGCD(x, y);
	r = x / r * y;

	int m = a % r? 0 : 1;

	printf("%d", b / r - a / r + m);
}