1248: HH的军训[容斥定理]

柔光的暖阳◎ 2022-08-10 10:59 16阅读 0赞

## 1248: HH的军训 ##

时间限制: 1 Sec 内存限制: 128 MB  
提交: 92 解决: 11  
\[ [提交][Link 1]\]\[ [状态][Link 2]\]\[ [讨论版][Link 3]\]

## 题目描述 ##

大学里，最难忘的事情莫过于军训了，白白的HH童鞋就被无情的晒黑了，话说军训期间，最怕的就是被教官逗了，俗话说：珍爱生命，远离教官。教官总爱让同学们站方阵，由于同学很多，难免会有前面的同学挡着后面的同学，为了远离教官，大家都希望自己站的位置教官看不到自己，现在假如同学们站在一个有坐标点的矩阵上，同学们都站在每一组整数点上，而教官站在坐标（0,0）上，请问此时有多少个位置教官可以直接看到！

## 输入 ##

第一行输入一个T,代表T组测试数据。

接下来每行输入两个数字M,N，对于任意一个同学的坐标位置（x,y），都有1<=x<=M<=10000,1<=y<=N<=10000.

## 输出 ##

输出有多少位置教官能够看到。

## 样例输入 ##

21 42 3

## 样例输出 ##

## 提示 ##

对于测试数据2 3来说，此时由于位置（2,2）被（1,1）挡着，因此有一个位置教官看不到，故此有5个位置教官可以直接看到

**第一次不知道容斥定理，超时！！**

**留下超时代码。**

#include<stdio.h>
    #include<set>
    #include<algorithm>
    using namespace std;
    double f1(int x,int y)
    {
    	return (y*1.0)/(x*1.0);
    }
    int main()
    {
    	int T;
    	scanf("%d",&T);
    	while(T--)
    	{
    		set<double>q;
    		int x,y;
    		scanf("%d%d",&x,&y);
    		int i,j;
    		int ans=0;
    		for(i=1;i<=x;i++)
    		{
    			for(j=1;j<=y;j++)
    			{
    				q.insert(f1(i,j));
    			}
    		}
    		printf("%d\n",q.size());
    	}
    	return 0;
    }

以下是AC代码

<pre name="code" class="cpp">#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; 
    }

[Link 1]: http://122.206.78.33:8080/JudgeOnline/submitpage.php?id=1248
[Link 2]: http://122.206.78.33:8080/JudgeOnline/problemstatus.php?id=1248
[Link 3]: http://122.206.78.33:8080/JudgeOnline/bbs.php?pid=1248