首页 > ACM题库 > HDU-杭电 > HDU 4335-What is N?-数论-[解题报告]HOJ
2015
05-23

HDU 4335-What is N?-数论-[解题报告]HOJ

What is N?

问题描述 :

  (This problem is really old&easy and any acmer who is good at math may solve it in second)
  As we know, math is both intangible and specific. Today you are going to solve the following math problem:
  Given one non-negative integer b, one positive number P and one positive integer M, how many n could you find to satisfy the following 2 rules?
Trouble

  Here n! means n factorial , 0!=1,1!=1,2!=2,3!=6…,n!=(n-1)!*n

输入:

  In the first line of the input , we have one integer T indicating the number of test cases. (1 <= T <= 20)
  Then T cases follows.
  For every case, only 3 integers (b, P and M) in a single line. ( 0<=b<P, 1<=P<=10^5, 1 <= M <=2^64 �C 1 )

输出:

  In the first line of the input , we have one integer T indicating the number of test cases. (1 <= T <= 20)
  Then T cases follows.
  For every case, only 3 integers (b, P and M) in a single line. ( 0<=b<P, 1<=P<=10^5, 1 <= M <=2^64 �C 1 )

样例输入:

3
1 2 3
2 3 4
3 4 5

样例输出:

Case #1: 2
Case #2: 0
Case #3: 0

这题拿来以后以为是个神题…..T T

后来看了结题报告,说这是简单题,报告上说啥我没有理解。后来又看了看其他的东西,发现我有一个公式不知道,这个公式详见:http://hi.baidu.com/aekdycoin/item/e493adc9a7c0870bad092fd9

A^x=A^(x%phi(p)+phi(p)(mod p)…其中,x>=phi(m)

这样就可以通过公式求解,当x<phi(p)时,暴力求解。当x>=phi(p)时,把A用A%p替换,这样还是枚举暴力。。。

当p=1时,结果为m+1,由于m=2^64-1,所以当m为2^64-1时,要打印个字符串表示2^64,否则溢出,坑爹。。。。

另外,我当时做的时候WA了n多次,一个很2B的错误就是要用unsigned Long long……long long 的范围是2^63-1….

还有,我当时在处理p=2时搞了好半天。。。因为这个时候phi(p)=1,代码写不好的话,很容易杯具,样例给的很好,要把内个样例真正想明白才行,附代码:

#include <iostream>
#include <vector>

#ifdef _WIN32  
#define LL unsigned __int64  
#define out64 "%I64u"  
#define in64 "%I64u"  
#else  
#define LL unsigned long long  
#define out64 "%llu"  
#define in64 "%llu"  
#endif 

#define cl(a) memset(a,0,sizeof(a))
#define ss(a) scanf("%d",&a)
#define sl(a) scanf(in64,&a)
#define pb push_back

using namespace std;

const int N=100100;
int a[N],c[N],e[N],p,b;
LL m;

void prime()
{
    int i,j;
    for (i=2;i<N;i++)
        if (!a[i])
        {
            for (j=i*2;j<N;j+=i)
            {
                if (!a[j]) c[j]=i;
                a[j]=1;
            }
        }
}

void euler()
{
    int i,k;
    for (i=2;i<N;i++)
        if (!a[i]) e[i]=i-1;
        else   
        {
            k=i/c[i];
            if (k%c[i]==0) e[i]=c[i]*e[k];
            else e[i]=(c[i]-1)*e[k];   
        }
}

LL js(int x,int y)
{
    LL k=y,r=x,res=1;
    while (k>0)
    {
        if (k&1) res=(res*r)%p;
        r=(r*r)%p;
        k>>=1;
    }
    return res;
}

void print(int cas,LL z)
{
    printf("Case #%d: "out64"\n",cas,z);
}

int main()
{
    int T,i,cas;
    ss(T);
    prime();
    euler();
    for (cas=1;cas<=T;cas++)
    {
        ss(b);ss(p);sl(m);
        if (p==1)
        {
            if (m==18446744073709551615ULL) 
                printf("Case #%d: 18446744073709551616\n",cas);
            else print(cas,m+1);
            continue;
        }
        LL n=0,r=1,z=0;
        while (r<e[p]&&n<=m)
        {   
            if (js(n,r)==b) z++;
            n++;
            r*=n;
        }
        r=r%e[p];
        while (r!=0&&n<=m)
        {
            if (js(n,e[p]+r)==b) z++;
            n++;
            r=(r*n)%e[p];
        }
        if (n>m)
        {
            print(cas,z);
            continue;
        }
        if (n>0) n--;
        else if (b==0) z++;
        for (i=0;i<p;i++)
            if (js(i,e[p])==b)
            {
                LL k1=0,k2=0;
                if (m>=i) k1=(m-i)/p+1;
                if (n>=i) k2=(n-i)/p+1;
                z=z+(k1-k2);
            }
        print(cas,z);      
    }
    return 0;
}

 

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

参考:http://blog.csdn.net/liverpippta/article/details/8038098