2018京东校招笔试题-数据分析岗

题目大意是给出一个数字n，问a^b=c^d（1<=a、b、c、d<=n）这种式子的个数 1^2=1^1 1^1=1^2，这样的算两个，n<=100000.

首先分析题目，n的数据范围肯定是不能暴力的，从其他同学的反馈也表示这题暴力只能过20%

此题的规律在于，以一个较小的数字a当基底 将 a^p 和 a^q（设为m,n）当做新的底来计算m^c=n^d（m、n<=n），才能避免重复和漏判

比如4（2^2）和8（2^3），此时需要计算2和3的最小公倍数，然后再计算在幂指数不超过n的情况下满足4^c=8^d的式子的个数

比如从2^k开始，分别计算底为2^k和（2^（k+1）一直到2^s(2^s<=n&&s>=k+1))的式子，同时要将2^k置为已访问过，防止重复计算（2^k<=n）

#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
using namespace std;
const LL p = 1e9+7;
LL gcd(LL a,LL b){LL m=a,n=b,c;while(b!=0){c=a%b; a=b;  b=c;}LL sum=m*n/a;return sum;
}
LL mizhishu(LL n,LL k){LL sum=1;for(LL i =0;i>n;memset(hash_n,0,sizeof(hash_n));if(n==1){cout<<1<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！