首页 > ACM题库 > HDU-杭电 > HDU 2841- Visible Trees-数论-[解题报告]HOJ
2014
02-17

HDU 2841- Visible Trees-数论-[解题报告]HOJ

Visible Trees

问题描述 :

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.

输入:

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)

输出:

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)

样例输入:

2
1 1
2 3

样例输出:

1
5

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4135

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2841

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1695

 

hdu 4135

题目大意: 输入一个a,b,n。 让你求a~b中有多少个数和n互素。1和任何数都互素。

解题思路:

    看到题我们不可能对i属于a~b进行遍历,然后求i是否和n有公约数,有则不互素,无则互素。时间复杂度是n^2  n最大100000,TLE。

    这题要用到容斥定理。

    我们可以先这样想:[1,n]中有多少个数和m互素,可以转换成[1,n]中有多少个数和m不互素(假设这个值为ans),那么互素当然就为n-ans。

    问题就变成了求[1,n]中有多少个数和m不互素。

    假设n=12,m=30

    第一步:首先求出m的因子数(m的因子数为2,3,5)。

    第二步:[1,n]中 是m因子的倍数当然就不互素了。

             (2,4,6,8,10,12)->n/2   6个,  (3,6,9,12)->n/3  4个,(5,10)-> n/5 2个 。

             心急的就可能全部相加了。莫急,有没有发现里面出现了重复的,所以我们还要减去重复的。

            公式就是  n/2+n/3+n/5-n/(2*3)-n/(2*5)-n/(3*5)+n/(2*3*5).

    第三步: 关键的来了。这一步有多种方法,dfs,队列数组,位运算都行,队列数组比dfs快一点。这里我只讲第二种(队列数组), 我们可以用一个队列(数组也行)存储出现的分母,我们可以令队列的第一个元素为1,让每次出现的m的因子和队列中的元素一个一个相乘再存储到队列中,最后就会发现存储的元素就是我们上面的分母了。现在的问题又变成了我们时候用加什么时候用减,这里我们只需要每次存的时候在再乘一个(-1),就可以得到我们想要的结果了。

 题目说要求[a,b]中与n互素的,我们分别求出[1,b]与n互素的以及[1,a-1]与n互素的,两个相减就是答案了。

代码:

 

#include <iostream>
 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 #include <vector>
 using namespace std;
 vector<int>vt;
 
 __int64  n, a, b, res;
 __int64 que[1024];
 
 void fx()
 {
     vt.clear();
     res=n;
     for(int i=2; i*i<=n; i++)
     {
         if(res%i==0)
         {
           vt.push_back(i);
           while(res%i==0)
                res/=i;
         }
     }
     if(res>1)  vt.push_back(res);
 }
 
 __int64 cal(__int64 n, __int64 t)
 {
     int num=0;
     que[num++]=1;
     for(int i=0; i<vt.size(); i++)
     {
         int ep=vt[i];
         int k=num;
         for(int j=0; j<k; j++)
             que[num++]=ep*que[j]*(-1);
     }
     __int64 sum=0;
     for(int i=0; i<num; i++)
         sum+=t/que[i];
     return sum;
 }
 
 int main()
 {
     int  T, tcase=0;
     cin >> T;
     while(T--)
     {
         cin >> a >> b >> n;
         fx();
         __int64 ans=cal(n,b)-cal(n,a-1);
         printf("Case #%d: %I64d\n",++tcase,ans);
     }
     return 0;
 }

 

 

 

 hdu 2841

题目大意:   N*M的格点上有树,从0,0点可以看到多少棵树。

解题思路:

经画图推敲可以发现如果A1/B1=A2/B2那么就有一棵树看不到,所以就是找出Ai/Bi有多少种。

再可以发现A/B中,如果A,B有大于1的公约数,则A=A’*D B=B’*D,那么A/B=A’/B’,也就是存在另外一组数和这种相等,则问题转换成有多少对互质的数。

本题和上一题唯一的区别就是枚举i,从1-M中找与i互质的数,其中1<=i<=N。

容注意先预处理i的所有素因子,然后容斥求就可以了。

 

代码:

 

#include <iostream>
 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 #include <vector>
 using namespace std;
 
 const int maxn=100001;
 int que[maxn];
 vector<int>vt[maxn];
 
 void init()
 {
     for(int i=0; i<maxn; i++)
         vt[i].clear();
     for(int i=2; i<maxn; i++)
     {
         int t=i;
         for(int j=2; j*j<=i; j++)
         {
             if(t%j==0)
             {
                 vt[i].push_back(j);
                 while(t%j==0)
                    t/=j;
             }
         }
         if(t>1) vt[i].push_back(t);
     }
 }
 
 __int64 cal(int n, int s)
 {
     int num=0;
     que[num++]=1;
     for(int i=0; i<vt[s].size(); i++)
     {
         int ep=vt[s][i];
         if(ep>n) break;
         int k=num;
         for(int j=0; j<k; j++)
         {
             que[num++]=que[j]*ep*(-1);
         }
     }
     __int64 sum=0;
     for(int i=0; i<num; i++)
     {
         sum+=n/que[i];
     }
     return sum;
 }
 
 int main()
 {
     int T, n, m;
     init();
     cin >> T;
     while(T--)
     {
         scanf("%d%d",&n,&m);
         __int64 ans=n;
         for(int i=2; i<=m; i++)
             ans+=cal(n,i);
         printf("%I64d\n",ans);
     }
     return 0;
 }

 

 

 

hdu1695

题目大意:给你5个数a,b,c,d,k。x属于[a,b]y属于[c,d]。 问你有多少对(x,y)的公约数为k。  注意(x,y)和 (y,x)视为同一对。

解题思路:

 本题用到了容斥定理+数论素数筛选法+数论欧拉函数。 不失为一个好题。

 注意看清楚题目开头解释, 你可以假想a=c=1,有了这个就更简单了。 我们可以先令端点b,d分别除以k,b/=k,d/=k。

  b可能大于d,为了方便求解这里我们令d大于b,如果不是则互换。这样就只需要找[1,b],[1,d]中有多少对互素的数了。

我们令i从1~d进行遍历:

1、当i<=b时,可以直接用欧拉函数求出互素的对数。

2、当i>b时,利用容斥定理求[1,b]中与i互素的对数。

这里注意特判一下k=0的情况,藐视就是没注意这里running error time 几次。

本题用容斥定理我用了两种方法,队列数组和dfs,练练手感。队列数组比dfs快一倍。

代码:

 

#include <iostream>
 #include <cstdio>
 #include <algorithm>
 #include <cstring>
 #include <vector>
 using namespace std;
 
 const int maxn=100005;
 int que[maxn];
 bool color[maxn];
 int f[maxn], phi[maxn];
 vector<int>vt[maxn];
 
 void Eular()  //欧拉函数
 {
     phi[1]=1;
     int k, num=0;
     memset(color,false,sizeof(color));
     for(int i=2; i<maxn; i++)
     {
         if(!color[i])
         {
             f[num++]=i;
             phi[i]=i-1;
         }
         for(int j=0; j<num&&(k=i*f[j])<maxn; j++)
         {
             color[k]=true;
             if(i%f[j]==0)
             {
                 phi[k]=phi[i]*f[j]; break;
             }
             else
                 phi[k]=phi[i]*(f[j]-1);
         }
     }
 }
 
 void init()   //打表存因子
 {
     for(int i=2; i<maxn; i++)
     {
         int t=i;
         for(int j=0; f[j]*f[j]<=i; j++)
         {
             if(t%f[j]==0)
             {
                 vt[i].push_back(f[j]);
                 while(t%f[j]==0)
                    t/=f[j];
             }
         }
         if(t>1) vt[i].push_back(t);
     }
 }
 
 __int64 cal(int n, int s) //队列数组实现容斥定理
 {
     int num=0;
     que[num++]=1;
     for(int i=0; i<vt[s].size(); i++)
     {
         int ep=vt[s][i];
         if(ep>n) break;
         int k=num;
         for(int j=0; j<k; j++)
         {
             que[num++]=que[j]*ep*(-1);
         }
     }
     __int64 sum=0;
     for(int i=0; i<num; i++)
     {
         sum+=n/que[i];
     }
     return sum;
 }
 
 /*
 __int64 dfs(int a, int b, int cur)  //dfs实现容斥定理
 {
     __int64 res=0, k;
     for(int i=a; i<vt[cur].size(); i++)
     {
         k=b/vt[cur][i];
         res+=k-dfs(i+1,k,cur);
     }
     return res;
 }
 */
 
 int main()
 {
     int  a, b, c, d, k, T, tcase=0;
     Eular();
     init();
     cin >> T;
     while(T--)
     {
         scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
         if(k==0||k>b||k>d)
         {
             printf("Case %d: 0\n",++tcase); continue;
         }
         b=b/k, d=d/k;
         if(b>d) swap(b,d);
         __int64 ans=0;
         for(int i=1; i<=b; i++)
         {
             ans+=phi[i];
         }
         for(int i=b+1; i<=d; i++)
         {
             ans+=cal(b,i);
         }
         printf("Case %d: %I64d\n",++tcase,ans);
     }
     return 0;
 }

 

 

 

 

解题参考:http://www.cnblogs.com/kane0526/archive/2013/03/14/2795446.html


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。