京东非常精彩的幂数论题目 京东算法题---求幂

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了京东非常精彩的幂数论题目 京东算法题---求幂，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2482字，纯文字阅读大概需要4分钟。

内容图文

//这个才是正确的代码
作者：牛妹
链接：https://www.nowcoder.com/discuss/38889?type=0&order=3&pos=6&page=1
来源：牛客网

 

 

我们考虑去枚举n范围内的所有i,然后处理出i的幂那些数。 这个i就叫做底.

因为a^b=c^d 那么必然存在一个i s.t.下面的十字成立.这个证明做因数分解即可.
考虑对于i ^ x, 我们需要计算满足 (i ^ x) ^ c = (i ^ y) ^ d的数量,其中i ^ x, i ^ y <= n. 这些我们可以通过预处理出来。

 

然后对于(i ^ x) ^ c = (i ^ y) ^ d 其实意味着x c = y d, 意味着(x / y) = (d / c),(因为c,d可以做到互素) 其中x, y我们可以在预处理之后枚举出来,于是我们就可以借此计算出n范围内有多少不同这种c和d去满足等式。
其实就等于 n / max(x / gcd(x, y), y / gcd(x, y)),然后都累加进答案。gcd()表示最大公约数。
中间可能产生重复枚举,我们用一个set或者hash容器标记一下就好。

以上枚举对于2~sqrt(n)。最后对于大于sqrt(n)的部分,每个的贡献都是n。

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
 
public class Main {
 
  public final static long MOD = 1000000000 + 7;
 
  public static int max(int a, int b){
    return (a>b) ? a : b;
  }
 
  public static long gcd(long a,long b){
    return (a % b == 0) ? b : gcd(b,a%b);
  }
 
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    long n = in.nextInt();
    long ans = (long)1*n*(2*n-1) % MOD;//以1为底的个数,这个计算方式是 1.计算1**x=1**y 有n**2个 2.计算x**y=x**y这个有 n**2-n个 减去这个n表示第一种1里面1为底的已经算过了.
//3.所以下面讨论的情况是(i ^ x) ^ c = (i ^ y) ^ d且x!=y且i>1 这种情况.所以i从2取到根号n.

    Set<Integer> set  = new HashSet<>();
    for (int i = 2; i*i <= n; i++){ //下面的底至少是2,指数至少也是2,所以i**2<=n
      if ( set.contains(i)) continue;
      long tmp = i;
      int cnt = 0;
 
      while(tmp <= n) {
        set.add((int)tmp);
        tmp = tmp * i;
        cnt++;
      }//比如i取2,n=10的时候,那么set就是{2,4,8} cnt=3,之后4,8就不用算了,因为他们属于2这个底
 //cnt表示最高能取多少次幂.
      for(int k = 1; k <= cnt; k++) {
        for(int j = k + 1; j <= cnt; j++) {
          ans = (ans + n / (j / gcd(k, j) ) * (long)2 ) % MOD;
//(j / gcd(k, j) )这个操作就是把k,j这个分数变成互素的.
//比如k取1,j取2的时候,ans=ans+10/2*2:因为(i ^ x) ^ c = (i ^ y) ^ d且x!=y且i>1 所以这时也就是 (i ^ 1) ^ c = (i ^ 2) ^ d ,那么d最高取5个数分别是1到5,因为c<=10
//又如k=2,j=3, (i ^ 2) ^ c = (i ^ 3) ^ d ,那么d最高取3个分别是2,4,6,因为c<=10
//这个地方为什么这么计算呢因为k,j互素化之后,为了乘积xk=jy,那么x必须是j的倍数,但是x必须小于n
//所以x的取法只有n/j种.(这时j已经是(j / gcd(k, j) )了!)
        }
      }
 
    }
 
    System.out.println(ans);
  }
}

内容总结

以上是互联网集市为您收集整理的京东非常精彩的幂数论题目 京东算法题---求幂全部内容，希望文章能够帮你解决京东非常精彩的幂数论题目 京东算法题---求幂所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---