[第17期] 乘方[已总结]

northwolves

本期题目比较简单：

 

[此贴子已经被作者于2006-11-21 0:44:08编辑过]

fjlhgs

chrisfang

狼版主说这道题简单，但我感觉比前两期都困难了不少，主要就因为15位这个大数字，感觉就像是一个菜鸟过滤器，把我这类投机取巧的菜鸟都给滤出来了。

第二个函数比较简单，很快就出来了，而且速度也不错。倒是第一个函数虽然做法有不少，但是数字一大耗费时间就狂增。先是学习了菊花版主的数组课，来用数组做，结果数组的容量受限。后来用集合、字典等方法都大幅提升了速度，但还是到11、12位左右出现了速度障碍。想到了用递归做法，但函数递归调用我这个初学者还没见识过，只有尝试一下函数嵌套了。没想到试了一下自定义函数嵌套速度可以提升这么多，15位数字计算只要零点零几秒，虽然我知道更好的方法还会有很多，但我还是对现在这个算法速度比较满意了，所以先交卷吧。

感谢狼版主又让我新学了不少东西。

 

点评：

思路基本正确，但答案有误差。

[A1]=124时，[A8]=14,[A16]="121=11^2"

[A1]=125时，[A8]=15,[A16]="121=11^2"

第2个函数显然有错，请查找原因

原因找到：少写了一个+1，真晕。因为先做第二个函数，所以没做边界测试。后来做第一个函数倒是都加上1了。

Function maxpower() As String
Dim p#
p = CDbl(Range("a1").Value)
If p > 1 Then
For y = 2 To Int(Log(p) / Log(2)) + 1
For x = Int(p ^ (1 / y)) + 1 To 1 Step -1
s = x ^ y
If s <= p Then Exit For
Next x
If s > maxs Then
maxs = s
maxx = x
maxy = y
End If
Next y
maxpower = maxs & "=" & maxx & "^" & maxy
Else
maxpower = "1=1^2"
End If

Application.Volatile
End Function

[此贴子已经被作者于2006-11-21 8:58:26编辑过]

fjlhgs

第一次答题有错误，现重新答题。

fjlhgs

刚才的答题又错了，现重新上传。

点评：

思路基本正确，但答案有误差。

[A1]=124时，[A8]=14,[A16]="121=11^2"

[A1]=125时，[A8]=14,[A16]="121=11^2"

显然有错，请查找原因

[此贴子已经被northwolves于2006-11-20 21:23:34编辑过]

winland

试下, 速度还可以, 版主帮看看结果是不是对的.

Function powercount(dinput As Double) As Double
    Dim i As Integer
    Dim j As Integer
    Dim tmp As String
    Dim tmpArr(1 To 15) As Integer
    Dim dTmp As Double
    Dim dTmp1 As Double
    tmpArr(1) = 2
    tmpArr(2) = 3
    tmpArr(3) = 5
    tmpArr(4) = 7
    tmpArr(5) = 11
    tmpArr(6) = 13
    tmpArr(7) = 17
    tmpArr(8) = 19
    tmpArr(9) = 23
    tmpArr(10) = 29
    tmpArr(11) = 31
    tmpArr(12) = 37
    tmpArr(13) = 41
    tmpArr(14) = 43
    tmpArr(15) = 47
    powercount = 1
    For i = 15 To 1 Step -1
        dTmp = powerCount1(dinput, tmpArr(i))
        If dTmp > 0 Then
            powercount = powercount + dTmp - 1
            For j = i - 1 To 1 Step -1
                dTmp1 = powerCount1(dTmp, tmpArr(j))
                If dTmp1 > 0 Then
                    powercount = powercount - dTmp1 + 1
                End If
            Next j
        End If
    Next i
   
End Function

Function maxpower(dinput As Double) As String
    Dim tmp As Double
    Dim tmpStr As String
    Dim tmpL As Double
    tmpStr = ""
   
    For i = 2 To dinput
        tmpL = Int(dinput ^ (1 / i))
        If tmpL = 1 Then
            Exit For
        Else
            'when the difference is very small, some strange thing happen
            '------------------------------------------------------------
            If tmpL ^ i > dinput Then
                tmpL = tmpL - 1
            End If
            If (tmpL + 1) ^ i = dinput Then
                tmpL = tmpL + 1
            End If
            '-----------------------------------------------------------
            If tmpL ^ i > tmp Then
                tmp = tmpL ^ i
               
                tmpStr = tmpL & "^" & i
            End If
        End If
    Next i
    maxpower = tmp & "=" & tmpStr
End Function
Function powerCount1(dinput As Double, ibase As Integer) As Double
    Dim tmpL As Double
    tmpL = Int(dinput ^ (1 / ibase))
    If tmpL = 1 Then
        powerCount1 = 0
    Else
        If tmpL ^ ibase > dinput Then
            tmpL = tmpL - 1
        End If
        If (tmpL + 1) ^ ibase = dinput Then
            tmpL = tmpL + 1
        End If
        powerCount1 = tmpL
    End If
End Function

点评：

结果正确，各种情况考虑得比较周到。

[此贴子已经被northwolves于2006-11-20 21:29:03编辑过]

northwolves

附：我的解法：

Private Const p1 As String = "{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}"
Private Const p2 As String = "{6,10,14,15,21,22,25,26,33,34,35,38,39,46}"

Function powercount(ByVal r As Range) As Long
powercount = Evaluate("SUMPRODUCT(INT(" & r & "^(1/" & p1 & ")))-SUMPRODUCT(INT(" & r & "^(1/" & p2 & ")))")  '前者15个质数，1被计数15次，后者14个质数，1被计数14次，正好抵消
End Function

Function maxpower(ByVal r As Range) As String
Dim largest As Double, power As Byte, p3 As String
largest = Evaluate("MAX(INT(" & r & "^(1/" & p1 & "))^" & p1 & ")")
p3 = largest & "^(1/" & p1 & "))"
power = Evaluate("1/Max((INT(" & p3 & "=" & p3 & "*(1/" & p1 & "))")
maxpower = largest & "=" & largest ^ (1 / power) & "^" & power
End Function

 

northwolves

附：我的解法：

Private Const p1 As String = "{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}"
Private Const p2 As String = "{6,10,14,15,21,22,25,26,33,34,35,38,39,46}"

Function powercount(ByVal r As Range) As Long
powercount = Evaluate("SUMPRODUCT(INT(" & r & "^(1/" & p1 & ")))-SUMPRODUCT(INT(" & r & "^(1/" & p2 & ")))")  '前者15个质数，1被计数15次，后者14个质数，1被计数14次，正好抵消
End Function

Function maxpower(ByVal r As Range) As String
Dim largest As Double, power As Byte, p3 As String
largest = Evaluate("MAX(INT(" & r & "^(1/" & p1 & "))^" & p1 & ")")
p3 = largest & "^(1/" & p1 & "))"
power = Evaluate("1/Max((INT(" & p3 & "=" & p3 & "*(1/" & p1 & "))")
maxpower = largest & "=" & largest ^ (1 / power) & "^" & power
End Function

 

northwolves

2006 topcoder SRM305：

Problem Statement for PowerCollector
 
 
Problem Statement
     Your friends collect butterflies and stamps, but you collect numbers. Your collection of prime numbers is the finest in three counties, and your collection of transcendental numbers has been featured on national talkshows. Lately you've decided to start collecting powers, that is, numbers that can be written in the form MK, where M and K are positive integers with K > 1. However, you're wondering how big a box you'll need to hold them all. Given a number N, represented as a String, determine how many powers lie between 1 and N, inclusive. Return the number of powers as a String with no leading zeros.
 
 
Definition
     Class: PowerCollector
Method: countPowers
Parameters: String
Returns: String
Method signature: String countPowers(String N)
(be sure your method is public)
 
    
 
 
Constraints
- N will contain between 1 and 19 characters, inclusive.
- Each character in N will be a digit ('0'-'9').
- The first character in N will not be zero ('0').
- N will represent a number between 1 and 1000000000000000000 (10^18), inclusive.
 
Examples
0) 
     "10"
 
 
Returns: "4"
 
The powers between 1 and 10 are 1, 4, 8, and 9.
 
 
1) 
     "36"
 
 
Returns: "9"
 
The powers between 1 and 36 are 1, 4, 8, 9, 16, 25, 27, 32, and 36.
 
 
2) 
     "1000000000000000000"
 
 
Returns: "1001003332"

本题由以上题目改编，并把难度适当减低。

题目是问<=N的正整数中有多少个可以被写成M^k(M,k>1)的形式.N<=10^18

由于指数不大,所以可以枚举指数k,然后考虑有多少个b满足b^k<=N.这是b<=N^(1/k)，但是一个数可以被写成多种指数形式.需要去掉重复.

可以用容斥原理.我们只考虑 k = p1 * p2 * ... * pm的形式.如果k包含pi多次,很容易转化成这种形式.
对于某个k和B=[N^(1/k)],如果m为奇数,答案+B,否则-B.

northwolves

另附：

Perfect Power  A perfect power is a number of the form , where is a positive integer and . If the prime factorization of is , then is a perfect power iff . Including duplications (i.e., taking all numbers up to some cutoff and taking all their powers) and taking , the first few are 4, 8, 9, 16, 16, 25, 27, 32, 36, 49, 64, 64, 64, ... (Sloane's A072103). Here, 16 is duplicated since (1) As shown by Goldbach , the sum of reciprocals of perfect powers (excluding 1) with duplications converges, (2) The first few numbers that are perfect powers in more than one way are 16, 64, 81, 256, 512, 625, 729, 1024, 1296, 2401, 4096, ... (Sloane's A117453). The first few perfect powers without duplications are 1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 125, 128, ... (Sloane's A001597). Even more amazingly, the sum of the reciprocals of these numbers (excluding 1) is given by (3) (Sloane's A072102), where is the Möbius function and is the Riemann zeta function. The numbers of perfect powers without duplications less than 10, , , ... are 4, 13, 41, 125, 367, ... (Sloane's A070428).