在Java区看到一个比较有意思的题目，转过来大家讨论一下

Question

Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:  2^2=4, 2^3=8, 2^4=16, 2^5=32
  3^2=9, 3^3=27, 3^4=81, 3^5=243
  4^2=16, 4^3=64, 4^4=256, 4^5=1024
  5^2=25, 5^3=125, 5^4=625, 5^5=3125If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?翻译一下就是有一个m*n的矩阵，该矩阵的第一列是a^b,(a+1)^b,.....(a + n - 1)^b
第二列是a^(b+1),(a+1)^(b+1),.....(a + n - 1)^(b+1)
.......
第m列是(b + m - 1),(a+1)^(b + m - 1),.....(a + n - 1)^(b + m - 1)问这个矩阵里有多少不重复的数
（比如4^3 = 8^2，这样的话就有重复了)原题里面m和n的范围为100，这样的话就不用优化了，为了把问题搞难一些，让m和n都为10000吧。

Answer 1

本帖最后由 caozhy 于 2011-05-17 19:55:57 编辑

  

Answer 2

一个double型可以存 最大1.7E+308 ，要写个类来存喽。这个最大值精度是多少没研究过，10^40000你这里难啦。楼主难为我家的486了。

Answer 3

python 可以直接存储， 10000 ** 10000 

Answer 4

一个变量存10000，另一个变量再存10000
我们只需要知道 m^n 和 x^y 是否相等即可，又不用计算具体值

Answer 5

这也是要解决的问题之一呀，Btw，这个问题10000规模的，486也能算

Answer 6

依据 如果a<c a^b=c^d 那么存在k使a^k=c

假设 底数a 范围 m1 m2
指数b 范围 m3 m4

底数循环 推出条件 p^k>m2
当前 p
判断 是否计算过 若是continue
否 统计个数


统计个数方法
底数 p p^x … p^y
xy 由m3 m4 决定 是个集合

…

Answer 7

Pretty standard  YY puzzle, just use your imagination ... seems no classic algorithm but YY ~~~ haha

Answer 8

不想费啥时间写代码看规则实际是 n进制表示方式所以考虑过滤规则：这个数能否能转换为 以其他进制为底的数，log（n‘）或者Pow（n’）

Answer 9

数组项为
x^y  令x=p^q (x ,y ,p ,q都是整数，且p为最小的满足条件的最小整数)
那么每一项都能表示为p^(y * q) 即p^z （z=y*q）;
然后用这种形式来存放
只用比较 q ， z就可以了
比较的方法有了，那就和100 * 100没什么区别了

Answer 10

就像27楼gbb21所说的，这个问题没有什么现成的算法能够直接解决（也许有，我不知道），因此我们只能靠自己的思考来逐步优化。也就是说更多的算法知识在解决这个问题上可能是没用的。这个问题我有自己的一个解法，但很有可能不是最好的，因此也希望通过讨论，学习到更好的方法。所以大家有什么想法都可以提出来。

Answer 11

This is correct, time complexity is about O(n*log(m)) For n = 10000, m = 10000 should be solved instantly. 

Answer 12

a^b,          (a+1)^b,           .....  (a + n - 1)^b
a^(b+1),      (a+1)^(b+1),       .....  (a + n - 1)^(b+1)
.......
a^(b + m - 1),(a+1)^(b + m - 1), .....  (a + n - 1)^(b + m - 1)如果有两个数是相同的，那么它们一定不会在同一行，也不会在同一列
如果在同一行比如 i1行j1列 i2行j2列 （从0开始 ）
那么(a + i1)^(b+j1) = (a+i2)^(b+j2)
显然 a+i1 和 a+i2可表示为 p^q1 ,p^q2
而且有 q1*(b+j1)=q2*(b+j2)在查找的时候，可以只用查如下列
2^a1 - a, 2^(a1+1)-a ,... ,2^(a1+b1)-a  ( 2^a1 - a >0 , 2^(a1+b1)-a<=10000)
3^a2 - a, 3^(a2+1)-a ,... ,3^(a2+b2)-a  同上
....
100^a99-a,...100^(a99+b99)-a             然后比较行数与（ai+bj)的积

Answer 13

2<=m<=M, 当m>SQTR(M)，并且m 不等于 另一个数的幂时，不存在更大底数的相同幂的数值
所以当 M=10000  只需要检查 100 以内的数就可以了， 

Answer 14

具体说一下吧，因为我的方法是n*log(m)^2的。

Answer 15

        static void Main()
        {
            int m = 1000, n =10000;
            int sqrtM = (int)Math.Sqrt(m);
            int count = 0;
            byte[,] mn = new byte[m - 1, n - 1];
            int[] primes = getPrimes(n/2);
            
            for (int i = 2; i <= sqrtM; i++)
            {
                for (int j = 2; j <= n; j++)
                {
                    if (mn[i - 2, j - 2] == 0)
                    {
                        int x, y = j, k;
                        foreach (int p in primes)
                        {
                            int z = p;
                            k = (int)Math.Pow(i, z);
                            x = k;
                            while (x < m && x > 0 && z < j)
                            {
                                if (j % z == 0 && mn[x - 2, z - 2]==0)
                                {
                                    mn[x - 2, z - 2] = 1;
                                    count++;
                                    Console.WriteLine("{0}^{1} = {2}^{3}", i,j,x,z);
                                }
                                x *= k;
                                z += z;                                
                            }
                        }
                    }
                }
            Console.WriteLine("{0},{1}", i, count);
            }
            Console.WriteLine("{0}", (m-1)*(n-1)-count);
            Console.ReadKey();
        }        static int[] getPrimes(int max)
        {
            List<int> Primes = new List<int>();
            Primes.Add(2);
            for (int i = 3; i <= max; i += 2)
            {
                bool isprime = true;
                foreach (int tmp in Primes)
                {
                    if (i % tmp == 0)
                    {
                        isprime = false;
                        break; 
                    }
                }
                if (isprime)
                    Primes.Add(i);
            }
            return Primes.ToArray();
        }在比较大的数可以看出来，每个数基本只有一个可能的重复，所以还可以进一步优化

Answer 16

       static void Main()
        {
            int m = 100, n =100;
            int sqrtM = (int)Math.Sqrt(m);
            int count = 0;
            byte[,] mn = new byte[m - 1, n - 1];
            int[] primes = getPrimes(n/2);
            
            for (int i = 2; i <= sqrtM; i++)
            {
                for (int j = 2; j <= n; j++)
                {
                    if (mn[i - 2, j - 2] == 0)
                    {
                        int x;
                        foreach (int p in primes)
                        {
                            int z = p;
                            if (j % z != 0) break;
                            x = (int)Math.Pow(i,  z);
                            while (j % z == 0 && z <j && x>0 && x<=m)
                            {                                mn[x - 2, (j / z) - 2] = 1;
                                mn[i - 2, j - 2] = 1;
                                Console.WriteLine("{0}^{1} = {2}^{3}", i, j, x, (j / z));
                                z += z;
                                x = (int)Math.Pow(i,  z);
                            }
                        }
                    }
                }
            //Console.WriteLine("{0},{1}", i, count);
            }
            count = 0;
            for (int i = 2; i <= m; i++)
            {
                for (int j = 2; j <= n; j++)
                {
                    count += mn[i - 2, j - 2];
                }
            }            Console.WriteLine("{0}-{1} = {2}", (m - 1) * (n - 1), count, (m -1) * (n -1)- count);
            Console.ReadKey();
        }        static int[] getPrimes(int max)
        {
            List<int> Primes = new List<int>();
            Primes.Add(2);
            for (int i = 3; i <= max; i += 2)
            {
                bool isprime = true;
                foreach (int tmp in Primes)
                {
                    if (i % tmp == 0)
                    {
                        isprime = false;
                        break; 
                    }
                }
                if (isprime)
                    Primes.Add(i);
            }
            return Primes.ToArray();
        }改了一下，结果跟你还是不一样， 晚上回家再看看

Answer 17

        static void Main()
        {
            int m = 100, n =100;
            int sqrtM = (int)Math.Sqrt(m);
            int count = 0;
            byte[,] mn = new byte[m - 1, n - 1];
            int[] primes = getPrimes(n/2);
            
            for (int i = 2; i <= sqrtM; i++)
            {
                for (int j = 2; j <= n; j++)
                {
                    if (mn[i - 2, j - 2] == 0)
                    {
                        int x;
                        foreach (int p in primes)
                        {
                            int z = p;
                            x = (int)Math.Pow(i, z);
                            while ( z <j && x>0 && x<=m)
                            {
                                x = (int)Math.Pow(i, z);
                                if (j % z == 0)
                                {
                                    mn[x - 2,  (j/z) - 2] = 1;
                                    mn[i - 2, j - 2] = 1;
                                    Console.WriteLine("{0}^{1} = {2}^{3}", i, j, x, (j / z));
                                }
                                z += z;
                                x = (int)Math.Pow(i,  z);
                            }
                        }
                    }
                }
                Console.WriteLine("{0}", i);
            }
            count = 0;
            for (int i = 2; i <= m; i++)
            {
                for (int j = 2; j <= n; j++)
                {
                    count += mn[i - 2, j - 2];
                }
            }            Console.WriteLine("{0}-{1} = {2}", (m - 1) * (n - 1), count, (m -1) * (n -1)- count);
            Console.ReadKey();
        }        static int[] getPrimes(int max)
        {
            List<int> Primes = new List<int>();
            Primes.Add(2);
            for (int i = 3; i <= max; i += 2)
            {
                bool isprime = true;
                foreach (int tmp in Primes)
                {
                    if (i % tmp == 0)
                    {
                        isprime = false;
                        break; 
                    }
                }
                if (isprime)
                    Primes.Add(i);
            }
            return Primes.ToArray();
        }最后贴一次，刚才的还是有bug

Answer 18

    private void test()
    {
        int m = 8;     //列
        int n = 8;     //行
        int a = 1;
        int b = 1;        double[,] num = new double[n, m];        IList<double> list = new List<double>();
        IList<double> l = new List<double>();        for (int i = 2; i <= n; i++)
        {
            for (int j = 2; j <= m; j++)
            {
                double x = Math.Pow(a + i - 1, b + j - 1);                bool sta = false;
                for (int y = 0; y < list.Count; y++)
                {
                    if (list[y] == x)
                    {
                        l[y] = 0;
                        sta = true;
                    }
                }
                list.Add(x);
                if (sta)
                    l.Add(0);
                else
                    l.Add(x);                Response.Write(x);
                Response.Write(",");
            }
            Response.Write("<br />");
        }        foreach (double x in l)
            Response.Write(x + ",");
    }时间紧，没细调；
最后输出的结果，当为0时，则表示是重复的数据；
不知正确与否；

Answer 19

  Dim m As Int64 = 5
        Dim n As Int64 = 5
        Dim value As New Hashtable
        For a As Int64 = 2 To m
            For b As Int64 = 2 To n
                Dim c As String = Math.Pow(a, b)
                Console.Write(a & "^" & b & "=" & c.ToString() & ",")
                If IsNothing(value.Item(c)) Then
                    value.Add(c, a.ToString() & "^" & b)
                End If
            Next
            Console.WriteLine(" ")
        Next
        Console.WriteLine("数量：" & value.Count)
        Console.ReadLine()

Answer 20

99347607
using System;
using System.Diagnostics;
using System.Text;
using System.Threading;
using System.Collections.Generic;
using System.Linq;
class Program
{
    private const int N = 10000;
    private static Dictionary<int, int> funResult;
    private static HashSet<int> baseNumbers;
    static void Main(string[] args)
    {
        InitFunResult();
        InitBaseNumber();
        int s = (int)Math.Sqrt((double)N);
        int sum = 0, k = 0;
        for (int i = 2; i <= N; i++)
        {
            if (baseNumbers.Contains(i)) continue;
            if (i <= s)
                k = (int)Math.Log((double)N, (double)i);
            else
                k = 1;           
            sum += funResult[k];
        }
        Console.WriteLine(sum);
        Console.Read();
    }
    private static void InitFunResult()
    {
        int maxK = (int)Math.Log((double)N, 2d);
        funResult = new Dictionary<int, int>(maxK);
        HashSet<int> set = new HashSet<int>();
        int p;
        for (int i = 1; i <= maxK; i++)
        {
            if (i == 1)
                funResult[i] = 0;
            else
                funResult[i] = funResult[i - 1];
            for (int j = 2; j <= N; j++)
            {
                p = i * j;
                if (set.Add(i * j))
                {
                    funResult[i]++;
                }
            }
        }       
    }
    private static void InitBaseNumber()
    {
        baseNumbers = new HashSet<int>();
        int s = (int)Math.Sqrt((double)N);
        int p;
        for (int i = 2; i <= s; i++)
        {
            for (int j = 2; j <= s; j++)
            {
                p = (int)Math.Pow((double)i, (double)j);
                if (p <= N)
                    baseNumbers.Add(p);
                else
                    break;
            }            
        }        
    }
}using System;
using System.Diagnostics;
using System.Text;
using System.Threading;
using System.Collections.Generic;
using System.Linq;
class Program
{
    private const int N = 10000;
    private static Dictionary<int, int> funResult;
    private static HashSet<int> baseNumbers;
    static void Main(string[] args)
    {
        InitFunResult();
        InitBaseNumber();
        int s = (int)Math.Sqrt((double)N);
        int sum = 0, k = 0;
        for (int i = 2; i <= N; i++)
        {
            if (baseNumbers.Contains(i)) continue;
            if (i <= s)
                k = (int)Math.Log((double)N, (double)i);
            else
                k = 1;           
            sum += funResult[k];
        }
        Console.WriteLine(sum);
        Console.Read();
    }
    private static void InitFunResult()
    {
        int maxK = (int)Math.Log((double)N, 2d);
        funResult = new Dictionary<int, int>(maxK);
        HashSet<int> set = new HashSet<int>();
        int p;
        for (int i = 1; i <= maxK; i++)
        {
            if (i == 1)
                funResult[i] = 0;
            else
                funResult[i] = funResult[i - 1];
            for (int j = 2; j <= N; j++)
            {
                p = i * j;
                if (set.Add(i * j))
                {
                    funResult[i]++;
                }
            }
        }       
    }
    private static void InitBaseNumber()
    {
        baseNumbers = new HashSet<int>();
        int s = (int)Math.Sqrt((double)N);
        int p;
        for (int i = 2; i <= s; i++)
        {
            for (int j = 2; j <= s; j++)
            {
                p = (int)Math.Pow((double)i, (double)j);
                if (p <= N)
                    baseNumbers.Add(p);
                else
                    break;
            }            
        }        
    }
}

Answer 21

程序我大概看了一下，确实是n*log(m)的思路，很不错呀！
剩下的就是需要考虑一下不是从2开始的情况，比如从11到10000

Answer 22

先假设N为100吧.4 25 8 9 36这种底数不考虑 他等于2^2  5^5 2^3次方。以2为底，指数的取值可以为:
(2 3 4 5 6 7 8 9 10 11 12 …… 100）  99个(4 6 8 10 12 14 16 ……        200）  99 - 49 =50个  
（49个是重复出现的比如 4 6 8就是以前出现过的）(6,9,12,15,18,21,……          300）  99 - N个重复
(6 12 18 …… 102 108 都是重复的,假设N个 )因为100里面 2^6 = 64  所以 一共可以出现6此这样的情况
(2*6 3*6 4*6 5*6  ……  100*6)  也是 99-N个然后3-100都是这样的计算。

Answer 23

感觉把原来的2换成一个变量就可以了
没仔细验证，明天再研究，睡觉了。
using System;
using System.Collections.Generic;
class Program
{
    private const int M = 2;
    private const int N = 100;
    private static Dictionary<int, int> funResult;
    private static HashSet<int> baseNumbers;
    static void Main(string[] args)
    {
        InitFunResult();
        InitBaseNumber();
        int s = (int)Math.Sqrt((double)N);
        int sum = 0, k = 0;
        for (int i = M; i <= N; i++)
        {
            if (baseNumbers.Contains(i)) continue;
            if (i <= s)
                k = (int)Math.Log((double)N, (double)i);
            else
                k = 1;           
            sum += funResult[k];
        }
        Console.WriteLine(sum);
        Console.Read();
    }
    private static void InitFunResult()
    {
        int maxK = (int)Math.Log((double)N, (double)M);
        funResult = new Dictionary<int, int>(maxK);
        HashSet<int> set = new HashSet<int>();
        int p;
        for (int i = 1; i <= maxK; i++)
        {
            if (i == 1)
                funResult[i] = 0;
            else
                funResult[i] = funResult[i - 1];
            for (int j = M; j <= N; j++)
            {
                p = i * j;
                if (set.Add(i * j))
                {
                    funResult[i]++;
                }
            }
        }       
    }
    private static void InitBaseNumber()
    {
        baseNumbers = new HashSet<int>();
        int s = (int)Math.Sqrt((double)N);
        int p;
        for (int i = M; i <= s; i++)
        {
            for (int j = M; j <= s; j++)
            {
                p = (int)Math.Pow((double)i, (double)j);
                if (p <= N)
                    baseNumbers.Add(p);
                else
                    break;
            }            
        }        
    }
}

Answer 24

        static void Main()
        {
            int m = 10000, n = 10000;
            filter3(m, n);
            Console.ReadKey();        }
        static void filter3(int m, int n)
        {
            List<PowerNum> list = PowerNumList(m);
            list.Sort((x, y) =>
            {
                if (x.Base != y.Base)
                {
                    return x.Base - y.Base;
                }
                return y.Index - x.Index;
            });
            int count = 0;
            list.ForEach((x) =>
            {
                for (int i = n; i >= 2; i--)
                {
                    int lowindex= x.Index- 1;
                    while (lowindex > 0 && (x.Index * i) / lowindex <= n)
                    {
                        if ((x.Index * i) % lowindex == 0)
                        {
                            //Console.WriteLine("{0}^{1} ={2}^{3}", Math.Pow(x.Base,x.Index),i ,Math.Pow(x.Base,lowindex),i*x.Index/lowindex);
                            count++;
                            break;
                        }
                        lowindex--;
                    }
                }
            });
            Console.WriteLine("{0},{1}",count,(m-1)*(n-1)-count);
        }
        static List<PowerNum> PowerNumList(int max)
        {
            Dictionary<int, PowerNum> list = new Dictionary<int, PowerNum>();            for (int i = 2; i <= Math.Sqrt(max); i++)
            {
                int n = i, m = 1;
                while ((n *= i) <= max)
                {
                    m++;
                    if (!list.ContainsKey(n))
                    {
                        list[n] = new PowerNum() { Number = n, Base = i, Index = m };
                    }
                }
            }
            return list.Values.ToList();
        }        class PowerNum
        {
            public int Number { get; set; }
            public int Base { get; set; }
            public int Index { get; set; }
        }从写了一个算法，结果总算正确了，不过速度没有78楼的快，在上限为100000时很明显
78楼代码很奇怪，只有上限取 8 时结果错误

Answer 25

不光是质数, 6  10  12 14 18 都不可能转化成别的.
只有一种情况可以转化: x^y次方 (^这里表示乘方,不表示异或)
所以反向考虑,从所有底数里面排除 x^y 的值

Answer 26

所以只需要计算很少的数字，即使MN取到上百万也能很快计算出来        static void Main()
        {
            int m = 10000, n = 10000;
            //filter1(m, n);
            //filter2(m, n);
            filter3(m, n);
            Console.ReadKey();        }
        static void filter3(int m, int n)
        {
            int t = System.Environment.TickCount;
            List<PowerNum> list = PowerNumList(m);
            int maxIndex = list.Max((x) => {
                return x.Index;
            });
            Console.WriteLine(System.Environment.TickCount - t);
            t = System.Environment.TickCount;
            int[] indexCount = new int[maxIndex + 1];
            //int[] upIndexCount = new int[maxIndex + 1];
            for (int i = n; i >= 2; i--)
            {
                /*for (int index = maxIndex-1; index >= 2; index--)
                {
                    if (i % index == 0)
                    {
                        upIndexCount[index ]++;
                    }                }*/
                for (int index = maxIndex ; index >= 2; index--)
                {
                    int lowindex = index - 1;
                    while (lowindex > 0 && (index * i) / lowindex <= n)
                    {
                        //if (i % lowindex == 0 && lowindex>1) break;
                        if ((index * i) % lowindex == 0)
                        {
                            indexCount[index]++;
                            break;
                        }
                        lowindex--;
                    }
                }            }
            //for (int i = maxIndex - 1; i > 0; i--)
            //{
            //    upIndexCount[i] += upIndexCount[i + 1];
            //}
            Console.WriteLine(System.Environment.TickCount - t);
            int count = 0;
            list.ForEach((x) =>
            {
                count += indexCount[x.Index];// +upIndexCount[x.Index];
            });
            Console.WriteLine("{0},{1}",count,(m-1)*(n-1)-count);
        }
        static List<PowerNum> PowerNumList(int max)
        {
            Dictionary<int, PowerNum> list = new Dictionary<int, PowerNum>();            for (int i = 2; i <= Math.Sqrt(max); i++)
            {
                int n = i, m = 1;
                while ((n *= i) <= max)
                {
                    m++;
                    if (!list.ContainsKey(n))
                    {
                        list[n] = new PowerNum() { Number = n, Base = i, Index = m };
                    }
                }
            }
            return list.Values.ToList();
        }        class PowerNum
        {
            public int Number { get; set; }
            public int Base { get; set; }
            public int Index { get; set; }
        }
优化了一下，速度和jiabiao113的相当了，感觉还可以优化一下

Answer 27

        static void Main()
        {
            int m =3 ,n =5,M = 10000, N = 10000;
            filter3(m,n,M, N);
            Console.ReadKey();        }
        static void filter3(int s,int p, int m, int n)
        {
            List<PowerNum> list = PowerNumList(s, m);
            int maxIndex = 0;
            if(list.Count>0)maxIndex = list.Max((x) => {
                return x.Index;
            });
            int[] indexCount = new int[maxIndex + 1];
            for (int i = n; i >= p; i--)
            {
                for (int index = maxIndex ; index >= 2; index--)
                {
                    int lowindex = index - 1;
                    while (lowindex > 0 && index * i <= n * lowindex)
                    {
                        if ((index * i) % lowindex == 0)
                        {
                            indexCount[index]++;
                            break;
                        }
                        lowindex--;
                    }
                }            }
            int count = 0;
            list.ForEach((x) =>
            {
                count += indexCount[x.Index];
            });
            Console.WriteLine("{0},{1}",count,(m+1-s)*(n+1-p)-count);
        }
        static List<PowerNum> PowerNumList(int min, int max)
        {
            Dictionary<int, PowerNum> list = new Dictionary<int, PowerNum>();
            int sqrt = (int)Math.Sqrt(max);
            for (int i = min; i <= sqrt; i++)
            {
                int n = i, m = 1;
                while ((n *= i) <= max)
                {
                    m++;
                    if (!list.ContainsKey(n))
                    {
                        list[n] = new PowerNum() { Number = n, Base = i, Index = m };
                    }
                }
            }
            return list.Values.ToList();
        }        class PowerNum
        {
            public int Number { get; set; }
            public int Base { get; set; }
            public int Index { get; set; }
        }简单参数化就行了，去掉一个了除法，速度又快了一倍左右