KeepCode 4 解题报告-白红宇

KeepCode 4 解题报告

阅读量：5234 次

发布时间：2019-06-14

本文共 5109 字，大约阅读时间需要 17 分钟。

　　解题报告转摘录自： jian1573

　　原文链接：

ID	Origin	Title
Problem A
Problem B
Problem C
Problem D
Problem E
Problem F

Problem A

　　　红果果的欧拉函数;

View Code

View Code  #include 
      
           using namespace std;   //  x=p1^e1*p2^e2~~~pn^en  //phi(x)=(p1-1)*p1^(e1-1)*(p2-1)*p2^(e2-1)~~~(pn-1)*pn^(en-1) int phi(int m)   {       int i,s=1;       for(i=2;i*i<=m;i++)  {           if(m%i==0){               m/=i;               s*=i-1;               while(m%i==0) {                   m/=i;                   s*=i;               }           }       }       if(m>1)           s*=m-1;       return s;   }   int main()   {       int m;       while(cin>>m && m)         cout<
       
        <

Problem B

　　题意: 在1~a, 1~b中挑出(x,y)满足gcd(x,y) = k , 求(x,y) 的对数 , a,b<=10^5

　　思路: gcd(x, y) == k 说明x,y都能被k整除. 问题就可以转化为了求1~a/k 和 1~b/k间互质对数的问题;

　　我们让b>=a; 然后在[1....b/k]进行枚举,对于每一个i,我们只要在1...min(i-1,a)中找到与i互质数,记录个数,然后累加就得到结果了;

　　当i<=a/k时,我们可以直接用欧拉函数计算出与i互质的个数;

　　当i>a/k时,先将i质因数分解，求得[1,2,...,b/k] 里所有能被x的质因数整除的数的个数,即不互质的数的个数，然后用b/k减去即可;

　　而我们枚举i的质因数利用容斥原理, 容斥原理的具体如下：

　　区间中与i不互质的个数 = （区间中i的每个质因数的倍数个数）-（区间中i的每两个质因数乘积的倍数）+（区间中i的每3个质因数的成绩的倍数个数）-（区间中i的每4个质因数的乘积）+...

参考代码

View Code

View Code  #include
      
        #include 
       
         using namespace std; const int Max=100005; __int64 elur[Max];//存放每个数的欧拉函数值 int num[Max];//存放数的素因子个数 int p[Max][20];//存放数的素因子 void init()//筛选法得到数的素因子及每个数的欧拉函数值 {     elur[1]=1;     for(int i=2;i
        
         d)             swap(b,d);         b/=k;  d/=k;         __int64 ans=elur[b];         for(int i=b+1;i<=d;i++)             ans+=b-dfs(0,b,i);//求不大于b的数中,与i不互质的数的个数         printf("%I64d\n",ans);     }     return 0; }

Problem C

　　题意　　

　　:给定一个数N, 在[1,N)中的数M, gcd( M, N ) != 1, 且N%M != 0; 那么M就为N的一个special number, f( x ) 为统计 x 的special number的个数, 如果f( x )为奇数,那么x就为一个 real numbers. 求给定区间的real number数.

　　思路:

　　先看f(x),由题意得f(x)=x-phi( x ) - g(x)+1;( phi(x)为欧拉函数, g(x)为因子个数, +1 是因为1在phi(x)和g(x)中都算了 );

　　而real number只与f(x)的机偶性有关所以我们只讨论phi(x)和g(x)的奇偶性;

　　我们知道当x>2时phi(x)为偶数;

　　g(x)约数个数，我们由基本定理可得，x=p1^e1*p2^e2*…pn^en，而由计数方法易知 x的约数个数为 g(x)=(e1+1）*(e2+1)*…(en+1)的;

　　所以若要使 g(x) 为奇数，充要条件是（ei+1）都为奇数，即质数的幂都为偶数。所以此时 x必然是一个平方数;

　　综上，x为平方数，其约数个数为奇数；x为非平方数，其约数个数为偶数;

　　所以，当x>2时，若x为平方数，f(x)=x-奇-偶+1，要使f(x)为奇数，则x必为奇数；若x为非平方数，f(x)=x-偶-偶+1，

　　要使f(x)为奇数，则x必为偶数。当x=1或2时，f(x)=0.

　　综上，real numbers F(x) 的值为[3,x]中，奇数平方数+偶数非平方数的个数和，即偶数个数-偶数^2的个数+奇数^2的个数。

　　而偶数个数为 x/2-1，-1是为了把2减掉。偶数^2个数为 sqrt(x)/2，奇数^2个数为 ( sqrt(x)-(sqrt(x)/2) )-1，

　　这里-1是为了把1减掉。所以，化简后，F(x) = x/2-1+(sqrt(x)%2? 0: -1).

解题代码

View Code

View Code  #include
      
        #include
       
         #include
        
          #include
         
            __int64 get(__int64 x) {     if(x<=2) return 0;     return x/2-1+( (__int64)sqrt(1.0*x) %2? 0: -1);         }  int main() {     int T;     scanf( "%d", &T );     while(T--)     {         __int64 a, b;         scanf("%I64d%I64d", &a, &b);         printf("%I64d\n", get(b)-get(a-1));     } }

Problem D

　　思路: 由题意得N=2^x(x>=1)为偶数, 所以当 n 也为偶数时 N%n必为偶数, 故不存在;

　　当n为奇数时,利用同余定理求;

参考代码

View Code

View Code  #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            using namespace std;  int main( ) {     int N;     while( scanf( "%d", &N )!= EOF ){         if( N==1 || !(N&1) )             printf( "2^? mod %d = 1\n", N );         else{             int t=2, ans=1;             while( t != 1 ){                 t <<= 1;                 t%=N;                 ans++;             }              printf( "2^%d mod %d = 1\n",ans, N );                      }     }     return 0; }

Problem E

View Code

View Code  #include 
      
        #include 
       
         #include 
        
          int a[10005]={
    0}; void fun(  ) {     a[1]=a[0]=1;     for( int i=4; i<10005; i+=2 )         a[i]=1;     for( int i=3; i <= ( int )sqrt( 10005 ); i+=2 )     {         if(a[i]==0)             for( int j=i*i; j<10005; j += ( i+i ) )                 {                 a[j]=1;                 }     }       }  int main() {     fun( );     int n;     while( scanf( "%d", &n ) != EOF )     {         for( int i=n/2; i>1; i-- )         {             if( a[i]==0 && a[n-i]==0 )             {                     printf( "%d %d\n", i, n-i );                 break;                 }                 }         }     return 0; }

Problem F

　　思路:由题意可知,一定有解,而且解空间很小, 故可以枚举;

　　M=9983, n=A%M gcd( b,M )==1, ans=(A?B)%M,

　　则 n == (ans*b)%M;

　　因为: A%M == (A/B*B)%M==(A/B%M * B%M)%M== (ans*B%M)%M;

参考代码

View Code

View Code  #include 
      
         #include 
       
          #include 
        
           using namespace std;    int main(){      int T;      scanf("%d",&T);      while(T--){        __int64 n,b;        int x;        scanf("%I64d%I64d",&n,&b);        for(int i = 0;i < 9973; ++i){            if(( b * i - n ) % 9973 == 0){              x = i;              break;            }        }        printf("%d\n",x);       }      return 0;  }