刷题总结——math（NOIP模拟）

题目：

给定两个数字n,求有多少个数字b满足a^b和b^a同余于2^n,其中n<=30,a<=10^9,

题解:

挺巧妙的一道题···从中深深体会到打表的重要性···

首先根据ab奇偶性分情况讨论···若ab奇偶性不同的话肯定不会满足条件···因此要么ab同时为奇数··要么同时为偶数··

若ab同时为奇数··根据打表（证明考试时我是想不到的···）可得只有当ab相等时条件才成立··

若ab同时为偶数···当b<=n时可以直接暴力求··当b>n时,可以解得a^b肯定是可以被2^n整除的··因此我们要求b^a可以被2^n整除的个数··我们设b=2^k*c,其中c为奇数··可得b^a=2^(k*a)*(c^a),因此可以得出2^(k*a)>=2^n,推出k>=n/a,因此我们可以推出2^(n/a)肯定是整除b的··因此我们只需要找出在n到2^n的范围中有多少个数可以被2^(n/a)整除即可··注意这里的除法是向上取整

代码：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<ctime>

#include<cctype>

#include<cstring>

#include<string>

#include<algorithm>

using namespace std;

long long Bit[],mod,T,n,a;

inline long long ksm(long long a,long long b)

{

  long long ans=;

  while(b)

  {

    if(b%==)  ans=ans*a%mod;

    b/=;a=a*a%mod;

  }

  return ans;

}

inline void pre()

{

  Bit[]=;

  for(int i=;i<=;i++)  Bit[i]=Bit[i-]*;

}

inline long long R()

{

  char c;long long f=;

  for(c=getchar();c<''||c>'';c=getchar());

  for(;c<=''&&c>='';c=getchar())  f=f*+c-'';

  return f;

}

int main()

{

  //freopen("math.in","r",stdin);

  // freopen("math.out","w",stdout);

  pre();T=R();

  while(T--)

  {

    a=R();n=R();int ans=;mod=Bit[n];

    if(a%==)

    {

      cout<<""<<endl;

      continue;

    }

    else

    {

      for(int i=;i<=n;i++)

        if(ksm(a,i)==ksm(i,a))  ans++;

      int temp=(n+a-)/a;

      int up=Bit[n]/Bit[temp];

      int down=n/Bit[temp];ans+=up-down;

      cout<<ans<<endl;

    }

  }

  return ;

}

巴特西

刷题总结——math（NOIP模拟）

题目：

题解:

代码：

最新文章

热门文章