HPU1248: HH的軍訓 【容斥原理】

1248: HH的軍訓

Time Limit: 1 Sec   Memory Limit: 128 MB

Submit: 76   Solved: 8

[ Submit][ Status][ Web Board] [ Edit]

Description

大學裡，最難忘的事情莫過于軍訓了，白白的HH童鞋就被無情的曬黑了，話說軍訓期間，最怕的就是被教官逗了，俗話說：珍愛生命，遠離教官。教官總愛讓同學們站方陣，由于同學很多，難免會有前面的同學擋着後面的同學，為了遠離教官，大家都希望自己站的位置教官看不到自己，現在假如同學們站在一個有坐标點的矩陣上，同學們都站在每一組整數點上，而教官站在坐标（0,0）上，請問此時有多少個位置教官可以直接看到！

Input

第一行輸入一個T,代表T組測試資料。

接下來每行輸入兩個數字M,N，對于任意一個同學的坐标位置（x,y），都有1<=x<=M<=10000,1<=y<=N<=10000.

Output

輸出有多少位置教官能夠看到。

Sample Input

2 1 4 2 3

Sample Output

4 5

HINT

對于測試資料2 3來說，此時由于位置（2,2）被（1,1）擋着，是以有一個位置教官看不到，故此有5個位置教官可以直接看到

Source

河南理工大學第五屆ACM程式設計競賽

容斥原理模闆題。

#include <stdio.h> 
#include <string.h> 
  
int p[12], que[1024], k, back; 
  
void getp(int n) { 
    int i, j, t; k = 0; 
    for (i = 2; i * i <= n; ++i) 
        if (n % i == 0) { 
            p[k++] = i; 
            while (n % i == 0) n /= i; 
        } 
    if (n > 1) p[k++] = n; 
    back = 0; 
    que[back++] = -1; 
    for (i = 0; i < k; ++i) { 
        t = back; 
        for (j = 0; j < t; ++j) 
            que[back++] = p[i] * que[j] * -1; 
    } 
} 
  
int nop(int m) { 
    int sum = 0, i; 
    for (i = 1; i < back; ++i) 
        sum += m / que[i]; 
    return sum; 
} 
  
  
int main() { 
    int T, m, n, i, ans; 
    scanf("%d", &T); 
    while (T--) { 
        scanf("%d%d", &n, &m); 
        ans = n; 
        for (i = 2; i <= m; ++i) { 
            getp(i); 
            ans += n - nop(n); 
        } 
        printf("%d\n", ans); 
    } 
    return 0; 
} 
/************************************************************** 
    Problem: 1248 
    User: changmu 
    Language: C++ 
    Result: Accepted 
    Time:820 ms 
    Memory:820 kb 
****************************************************************/