HYSBZ-2190(欧拉函数）&&hdu-2814(容斥原理)

青旅半醒 2022-06-09 00:17 146阅读 0赞

问题描述：

作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N \* N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 　　 ![71ac0e5674cc136081b0c73a270897c1_v_1503295908][] 　　现在，C君希望你告诉他队伍整齐时能看到的学生人数。

Input

共一个数N。

Output

共一个数，即C君应看到的学生人数。

Sample Input

Sample Output

HINT :1<=N<=40000

题目题意：题目给你一个数字N，问我们最多能在这个N\*N的矩阵中看到多少人！

题目分析：刚刚看到的时候有点蒙，我们仔细分析一下，我们为什么不能看到所有的人了，因为有些人被挡住了，为什么会被档住了，因为它前面还有人

即：在一条直线上我们只能看到最前面的人，也就是说，我们现在有几条直线，就能看到几个人。

我们把样例模拟一下：

3  O O O O

2   O O O O

1   O O O O

0   O O O O

0  1  2  3

我们现在把所有可以看到的人，坐标写出来：

(1,1)  (2,1)  (3,1) (3,2)

(1,2) (1,3)  (2,3)

(1,0) (0,1)

不难发现一点，人关于对角线分布，那我们就现在只考虑下半部分:

除了(1,0)这个点特殊外，我们发现其他点的横纵坐标互质（不信的话，可以多花几组）

我们有了这个思路，再来仔细看一下：

假设有点(k\*x,k\*y) 那么我们可以看到这个点吗，一定不行,因为再它前面有(x,y) ,他们俩在一条直线上。

好了，答案很明显了，就是求（x,y)里面互质的对数，根据对称性乘以2，然而对角线是被算了俩次的，所以减一，然后还要加上特殊的(1,0) (0,1） 俩点就行了。

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    
    const int maxn=40000+10;
    int euler[maxn];
    void get_euler()
    {
        for (int i=1;i<maxn;i++)
            euler[i]=i;
        for (int i=2;i<maxn;i++) {
            if (euler[i]==i)
                for (int j=i;j<maxn;j+=i)
                euler[j]=euler[j]/i*(i-1);
        }
    }
    
    int main()
    {
        int n,sum;
        get_euler();
        while (scanf("%d",&n)!=EOF) {
            n--;
            sum=0;
            for (int i=1;i<=n;i++)
                sum+=euler[i];
            printf("%d\n",sum*2+1);;
    
        }
        return 0;
    }

问题描述:

There are many trees forming a m \* n grid, the grid starts from (1,1). Farmer Sherlock is standing at (0,0) point. He wonders how many trees he can see.   
  
If two trees and Sherlock are in one line, Farmer Sherlock can only see the tree nearest to him.

Input

The first line contains one integer t, represents the number of test cases. Then there are multiple test cases. For each test case there is one line containing two integers m and n(1 ≤ m, n ≤ 100000)

Output

For each test case output one line represents the number of trees Farmer Sherlock can see.

Sample Input

2
    1 1
    2 3

Sample Output

1
    5

题目题意:问题和上一题是差不多的，只是正方形N\*N变成了长方形m\*n但是解决问题的思想还是没有变，但是这时候有个问题就是n与m不相等，所以欧拉函数就用不了了，但是我们还有容斥原理啊，我们就利用容斥原理来求互质对数

利于在1到n里面求与m互质的对数，我们把m质因子分解，

m=p1^a1\*p2^a2\*\*\*\*\*\*\*pn^an

那么能被p1整除的数就不互质了，有n/p1个，同理可求其他的，但是这里面有重复，例如6可以被2整除，还可以被3整除，这里用到了容斥原理了。

这是我之前写的:

[点击打开链接][Link 1]

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #define ll long long
    using namespace std;
    
    const int maxn=1e5+10;
    int prime[maxn],cnt;
    bool vis[maxn];
    void get_prime()
    {
        memset (vis,true,sizeof (vis));
        vis[1]=false;
        for (int i=2;i<maxn;i++) {
            if (vis[i]) prime[cnt++]=i;
            for (int j=0;j<cnt&&i*prime[j]<maxn;j++) {
                vis[i*prime[j]]=false;
                if (i%prime[j]==0) break;
            }
        }
    }
    int factor[100][2],fcnt;
    void get_factor (int m)//分解质因子
    {
        fcnt=0;
        for (int i=0;i<cnt&&prime[i]*prime[i]<=m;i++) {
            if (m%prime[i]==0) {
                factor[fcnt][0]=prime[i];
                while (m%prime[i]==0) {
                    factor[fcnt][1]++;
                    m=m/prime[i];
                }
                fcnt++;
            }
        }
        if (m!=1) {
            factor[fcnt][0]=m;
            factor[fcnt++][1]=1;
        }
    }
    int get_ans(int n,int m)//容斥原理
    {
        get_factor(m);
        ll ans=0;
        for (int i=1;i<(1<<fcnt);i++) {//这个是状态压缩写的，用dfs写也可以
            int cnt=0;
            ll temp=1;
            for (int j=0;j<fcnt;j++) {
                if (i&(1<<j)) {
                    cnt++;
                    temp=temp*factor[j][0];
                }
            }
            if (cnt&1)
                ans+=n/temp;
            else
                ans-=n/temp;
        }
        return n-ans;
    }
    int main()
    {
        int t;
        get_prime();
        scanf("%d",&t);
        while (t--) {
            int n,m;
            ll ans=0;
            scanf("%d%d",&n,&m);
            if (n>m) swap (n,m);//把小的作为寻找区间
            for (int i=1;i<=n;i++)
                ans+=get_ans(m,i);//挨个去找
            printf("%I64d\n",ans);
        }
        return 0;
    }

[71ac0e5674cc136081b0c73a270897c1_v_1503295908]: https://odzkskevi.qnssl.com/71ac0e5674cc136081b0c73a270897c1?v=1503295908
[Link 1]: http://blog.csdn.net/wust_cyl/article/details/77149913