京东第二题 a^b = c^d，求大神分享思路

n = int(raw_input()) resultDict={} for i in range(1, n+1): for j in range(1, n+1): temp = i**j if temp in resultDict: resultDict[temp]+=1 else: resultDict[temp] = 1 result=0 for _,v in resultDict.iteritems(): result+=v+v*(v-1) print result%1000000007 暴力O(n^2)，过40

同问...只过10%...

n*(2*n-1) 20%…… 我也不会，不过提供一下我的思路互相交流吧。 1.  首先是自身的情况，就是自己等于自己，比如1^1 = 1^1, 2^3 = 2^3 这种， 这种情况的个数是 n*n, 2.  再加上 1^x, x为任意值 ，这种情况也是 n*n， 但其中包含这种 1^2 = 1^2, 1^4 = 1^4，这种与1重复的情况，减去。 得到 n*(n-1)。 3. 现在没有考虑到的情况就是4、8、9这种 2^2, 2^3, 3^2的情况，我写了一个求约数的函数，但看一眼要求一秒完成感觉通过遍历得到这些数必然超时，就没有想到好的处理方法。

result(n) = result(n-1)+4n-3+··· ···时间不够了，后来想了想，如果n=2a,3b,4c... 1^n,2^n,...,(n-1)^n,n^n (1^2)^a,(2^2)^a,...,(x^2)^a, (1^3)^b,(2^3)^b,...,(y^3)^a, (1^4)^a,(2^4)^a,...,(z^4)^a, ... 只要算出x,y,z...

30%

直接 return  6；    10%

老哥们 看看我的 交卷后写的 应该能AC package jindong; import java.util.Scanner; public class Demo2 { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { int n = in.nextInt(); //a b c d互不相同的情况 有多少种 long count = 0; w :for (int i = 2; i <= n; i++) { int t = 0; for (int j = 2; j <= n; j++) { if (Math.pow(j, i) <= n) t++; else { count += (n / i) * t * 2; break w; } } } //加上 a和c都为1 和 a和c都不为1且a和c相等 b和d相等 两种情况 count += n * n + (n - 1) * n; System.out.println(count % 1000000007); } } }

采用x*y等于lg(k)/lg(i)

public class Test {public static final int f = 1000000007;public static int num(int n){ if(n==1) return 1; return (num(n-1)+4n-3+sub1(n)+sub2(n))%f;}private static int sub1(int n){ int r=0; for(int i=2;i<=n/2;i++){ if(n%2==0){ int m = (int)Math.pow(n, 1.0/i) - 1; if(m>0) r += 2m; } } return r;}private static int sub2(int n){ int r=0; int le = (int)(Math.log(n)/Math.log(2)); for(int i=2;i<le;i++){ double d = Math.pow(n, 1.0/i); if(d-(int)d<0.000000001){ int m = (n-1)/i; r += 2*m; } } return r;}}