首页 > 试题广场 >

求幂

[编程题]求幂

热度指数：1122 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

东东对幂运算很感兴趣,在学习的过程中东东发现了一些有趣的性质: 9^3 = 27^2, 2^10 = 32^2
东东对这个性质充满了好奇,东东现在给出一个整数n,希望你能帮助他求出满足 a^b = c^d(1 ≤ a,b,c,d ≤ n)的式子有多少个。
例如当n = 2: 1^1=1^1
1^1=1^2
1^2=1^1
1^2=1^2
2^1=2^1
2^2=2^2
一共有6个满足要求的式子

输入描述:

输入包括一个整数n(1 ≤ n ≤ 10^6)

输出描述:

输出一个整数,表示满足要求的式子个数。因为答案可能很大,输出对1000000007求模的结果

示例1

输入

输出

算法知识视频讲解

spMoon

 照 北交大李国杰 同学答案改的py3版本，通过率90%，感觉是python数值计算精度的问题导致的计算错误；
希望解决了这个问题的同学指教
import math
def gcd(a,b):
    a,b=min(a,b),max(a,b)
    for i in range(1,a+1):
        if a%i==0 and b%i==0:
            cd=i
    return cd
n=int(input())
mode=int(1e9+7)
rec=[0]*(n+1)#record list
res=n*(2*n-1)%mode
for i in range(2,n+1):
    if rec[i]:
        continue
    rec[i]=1
    lgn=math.floor(math.log(n,i))
    for lga in range(1,lgn):
        rec[i**lga]=1
        for lgc in range(lga+1,lgn+1):
            res+=(n//(lgc//gcd(lga,lgc))*2)
            res=res%mode
print(res)

发表于 2018-08-31 15:14:44 回复(0)

起个昵称真难201807192251996

import math
n=int(input())
count=0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            if math.pow(i**j,1/k) in range(1,n+1):
                count=count+1   
print(count)

编辑于 2018-09-06 09:36:29 回复(4)

无关代码

# 回复 spMoon
# 非常感谢你将java改成python3版本
# 我是基本照抄你的代码，懒得大改，然后修改了一点点
# 你的代码用的是math.floor取整，而北交大李国杰同学用的是round取整，这就是你俩不一致的地方，修改后准确率达到100%

import math
def gcd(a,b):
    a,b=min(a,b),max(a,b)
    for i in range(1,a+1):
        if a%i==0 and b%i==0:
            cd=i
    return cd
n=int(input())
mode=int(1e9+7)
rec=[0]*(n+1)
res=n*(2*n-1)%mode
for i in range(2,n+1):
    if rec[i]:
        continue
    else:
        rec[i]=1
        lgn=round(math.log(n,i))
    if pow(i,lgn)>n:
        lgn = lgn-1
    for lga in range(1,lgn):
        rec[i**lga]=1
        for lgc in range(lga+1,lgn+1):
            res+=(n//(lgc//gcd(lga,lgc))*2)
            res=res%mode
print(res)

发表于 2019-04-27 11:49:58 回复(0)

一生平安777777


	
	
		import java.util.*;
 
public class Main {
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long out = 0;
        int[] already = new int[n + 1];
        out += ((long)n) * n; // a=c=1
        out += ((long)n) * (n - 1);// a=c!=1时
        for (int i = 2; i <= n; i++)// 底数遍历
        {
            if (already[i] == 0) {//算过的就不用算了
                long counti = 0;
                int logn = (int) Math.round(Math.log(n) / Math.log(i));// log以i为底 可能有舍入误差
                if (Math.pow(i, logn) > n)
                    logn--;
                for (int loga = 1; loga <= logn; loga++) {
                    for (int logc = 1; logc <= logn; logc++) {
                        if (loga != logc) {
                            int comFactor = 1;// 最大公因数
                            int smaller = loga > logc ? logc : loga;
                            int bigger = loga < logc ? logc : loga;
                            for (int com = 1; com <= smaller; com++) {
                                if (loga % com == 0 && logc % com == 0) {
                                    comFactor = com;
                                }
                            }
                            counti += (n / (bigger / comFactor));
                        }
                    }
                    already[(int) Math.pow(i, loga)] = 1;
                }
                out += counti;
            }
        }
        System.out.println(out % 1000000007L);
    }
}
		
			
		

	

	
		
	

	
		//在答题区看到了更好的答案 留给大家研究研究
	

	
		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*(n*2-1) % MOD;
    Set<Integer> set  = new HashSet<>();
    for (int i = 2; i*i <= n; i++){
      if ( set.contains(i)) continue;
      long tmp = i;
      int cnt = 0;
   
      while(tmp <= n) {
        set.add((int)tmp);
        tmp = tmp * i;
        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;
        }
      }
   
    }
   
    System.out.println(ans);
  }
}

编辑于 2018-09-16 22:21:52 回复(2)

ring201807131322254

importmath

n=int(input())

count=0

for i in range(1,n+1):

for j in range(1,n+1):

for k in range(1,n+1):

if math.pow(i**j,1/k) in range(1,n+1):

count=count+1

print(count)

发表于 2018-09-09 17:14:28 回复(0)

漂亮的反击

import java.util.Scanner;
public class Test01 {

    public static void main(String args[]) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        System.out.println(number(n));
    }

    public static int pow(int a,int b) {
        int cur=a,ans=1;
        while(b!=0) {
              if(b%2==1)
                ans*=cur;
                cur*=cur;
              b/=2;

        }return ans;
    }
    public static int number(int n) {
        int a=1,b,c,d;
        int count=0;
        while(a<=n) {
            b=1;
            while(b<=n) {
                c=1;
            while(c<=n) {
                d=1;
            while(d<=n) {
                if(pow(a, b)==pow(c,d)) {
                    count++;
            }
                d++;
                }
            c++;
            }
        b++;
    }
    a++;
            }
        return count;
        }

}

本地编译器没有问题，但是实际测试只通过了20%

有尝试改变输入类型为long，还是不行。。。。

发表于 2018-09-09 15:46:47 回复(0)

Jean12

powers = {} 
for i in range(1,n+1):     
    for j in range(1,n+1):         
        power = i**j        
        v = powers.get(power,0)         
        powers[power] = v+1 
nums = 0 
for value in powers.values():     
    nums += value**2 
print(nums)

用字典之后空间超了。。。

编辑于 2018-09-08 18:47:47 回复(0)

花生201806211807889


	
	
		if__name__=='__main__':
	

	
		    N=raw_input()
	

	
		    N=int(N)
	

	
		    NUM=dict()
	

	
		    D=dict()
	

	
		    for k in range(2,N+1):
	

	
		        for i in range(1,N+1):
	

	
		            m=pow(k,i)
	

	
		            if m not in D:
	

	
		                D[m]=1
	

	
		                NUM[m]=pow(D[m],2)
	

	
		            else:
	

	
		                D[m]=D[m]+1
	

	
		                NUM[m]=pow(D[m],2)
	

	
		    del m
	

	
		    print(sum(NUM.values())+N*N)%1000000007

发表于 2018-08-17 22:07:23 回复(1)

海边的贝壳0

  import math 
  n = input() 
  n = int(n) 
  count=0 
  for i in range(1,n + 1): 
      for j in range(1,n + 1): 
          for k in range(1, n + 1): 
              if math.pow(i ** j,1 / k) in range(1,n + 1): 
                  count += 1 
  print(count)
 

发表于 2018-07-22 20:56:09 回复(2)

无心学习只想种地

#include<iostream>
#include<math.h>
using namespace std;
int main()
{
long long n;
cin >> n;
long long m = 2 * n*n - n;
//cout << m << endl;
long el = 0;
long cal_num(long long n, long el);
long l = cal_num(n,el);
cout << m + l;
return 0;
}

long cal_num(long long s, long el)
{
int n = 0, *mat, size = (int)sqrt(s)*(int)log10(s);
mat = (int*) malloc(sizeof(int)*size);
for (int i = 2; i <= sqrt(s); i++)
{
int flag = 0;
for (int k = 0; k < size; k++)
{
if (i == mat[k]) {
flag = 1;
break;
}
}
if (flag == 1) continue;
int c = log10(s)/log10(i);
for (int p = 2; p < c + 1; p++)
{
long s1 = pow(i,p);
mat[n] = s1;
n = n + 1;
el = el + s / p * 2;
if (p > 2)
{
for (int j = 2; j < p; j++)
{
int cal_gbs(int a, int b);
int gys = cal_gbs(j, p);
el = el + (s*j) / gys * 2;
}
}
}
}
//cout << el << endl;
return el;
}

int cal_gbs(int a, int b)
{
for (int m = a;; m++)
{
if (m%a == 0 && m%b == 0)
{
return m;
break;
}
}
}

编辑于 2018-05-29 21:41:04 回复(2)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师京东 2018 PHP工程师数学 Java工程师

上传者：小小

难度：

10条回答 60收藏 6409浏览

通过挑战的用户

牛客51512...

2023-03-11 11:37:53
牛客43932...

2022-09-16 23:06:24
wood201...

2022-08-31 09:57:30
SuperNLPer

2022-08-26 23:14:07
忧伤的斑马面试中

2022-08-19 12:33:33

求幂

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题