首页 > ACM题库 > HDU-杭电 > HDU 4215-Number Theory?-数论-[解题报告]HOJ
2015
05-23

HDU 4215-Number Theory?-数论-[解题报告]HOJ

Number Theory?

问题描述 :

In number theory, for a positive number N, two properties are often mentioned, one is Euler’s function, short for E(N), another is factor number, short for F(N).
To be more precise for newbie, here we recall the definition of E(N) and F(N) again.
E(N) = |{i | gcd(N, i) = 1, 1 <= i <= N}|
F(N) = |{i | N % i = 0, 1 <= i <= N}|
Here |Set| indicates the different elements in the Set.
As a number fanaticism, iSea want to solve a simple problem now. Given a integer N, try to find the number of intervals [l, r], l is no bigger than r obviously, strictly fit in the interval [1, N]. It’s a piece of cake for clever you, of course. But here he also has another troublesome restrict:
Crash and Go(relians)

输入:

The first line contains a single integer T, indicating the number of test cases. Each test case includes one integer N.

Technical Specification
1. 1 <= T <= 1 000
2. 1 <= N <= 1 000 000 000

输出:

The first line contains a single integer T, indicating the number of test cases. Each test case includes one integer N.

Technical Specification
1. 1 <= T <= 1 000
2. 1 <= N <= 1 000 000 000

样例输入:

2
2
9

样例输出:

Case 1: 1
Case 2: 6

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

题意为给出数字N,找出对应区间[L,R]的个数,使得1<=L<=R<=N,且对于该区间内的每一个值i(L<=i<=R)的两个指标:欧拉函数E(x)和因数个数F(x) sum(E(i))=sum(F(i)).

月赛第8题 但是想了好久如何去实现这个算法,因为F(n)和E(n)的求解复杂度基本都为nlogn,而题目时限1s 最大数据达到1e9.从内存和时间方面都不可能实现具体的求解。
看到这种题应该是打表。但是一直不是很清楚原理。
搜了下OEIS

找到四张图,应该可以比较清楚地了解

Number Theory?Number Theory?

从点的密度的所在的数量级上得知二者的发散程度相差较大。

下面两者的sum分布

Number Theory?Number Theory?

知二者大概在100-200左右就有了较大的分异,从而在200之后不会相等,不会出现新的区间,只需处理前面200的数据。

朴素打表前1000的答案,发现在30之后的答案就不会增长了。

只需处理前30的数据 剩余数据使用ans[30]即可。

//[hdu 4215]Number Theory? 数论+打表 by ahm001

#include<cstdio>
#include<cstring>
#define N 30
using namespace std;
int i,o,p,j,k,l,n,m,t,r; 
int e[40];
int f[40];
int ans[40];

int gcd(int x,int y)
{
	if (y==0) return x;
	return gcd(y,x%y);
}

int main()
{
    memset(ans,0,sizeof(ans));
    memset(e,0,sizeof(e));
    memset(f,0,sizeof(f));
    for (i=1;i<=N;i++)
        for (j=1;j<=i;j++)
        {
             if (gcd(i,j)==1) ++e[i];
             if (gcd(i,j)==j) ++f[i];
        }
    for (i=1;i<=N;i++)
        {
             e[i]+=e[i-1];
             f[i]+=f[i-1];
        }
    for (i=1;i<=N;i++)
        for (j=i;j<=N;j++)
        if(e[j]-e[i-1]==f[j]-f[i-1])
        {
            ans[j]+=1;
        }
    for (i=1;i<=N;i++) ans[i]+=ans[i-1];
    
    
	/*打表 更改N=1000
	for (i=1;i<=N;i++)
	printf("%d ",ans[i]); 
	*/
    scanf("%d",&t);
    p=0;
    for (;t;t--)
    {
        scanf("%d",&i);
        printf("Case %d: ",++p);
        if (i<=N) printf("%d\n",ans[i]);
        else printf("%d\n",ans[N]);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ahm001/article/details/23303429