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?
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?
long m=System.currentTimeMillis();
for(int i=2;i<=100;i++)
for (int j=2;j<=100;j++)
set1.add((Double)Math.pow(i,j));
System.out.println(set1.size());
long n=System.currentTimeMillis();
System.out.print(n-m);
这个方法可行用时16毫秒 符合要求吗？
用double+Set的可能要死翘翘的。特别是使用double计算7^100，可能根本就不等于49^50。
2, 100
};
int[] bLimit = {
2, 100
};
int total = (aLimit[1] - aLimit[0] + 1) * (bLimit[1] - bLimit[0] + 1);
for (int a = aLimit[0]; a <= aLimit[1]; a++) {
int x = (int) Math.pow(a, bLimit[0]);
for (int b = bLimit[0]; b <= bLimit[1]; b++) {
if (x > bLimit[1]) {
break;
}
if (x >= aLimit[0] && x <= aLimit[1]) {
for (int n = bLimit[0]; b * n <= bLimit[1]; n++) {
total--;
System.out.printf("%d^%d=%d^%d%n", x, n, a, b*n);
}
}
x *= x;
}
}
System.out.println(total);
}
假设，x=a^b
那么，x^n = a^(b*n)
只要排除所有2 ≤ b*n ≤ 100的个数即可
final int max = 100;
int[] rs = new int[max];
int[] flag = new int[max];
BigInteger bm = BigInteger.valueOf(max);
for (int i=2;i<=max;i++) {
for (int j=2;j<=max;j++) {
int f = (1<<j);
if ((flag[i-1]&f)!=f) {
BigInteger b = BigInteger.valueOf(i);
BigInteger r = b.pow(j);
if (r.max(bm)==bm) {
int t = max/j;
for (int n=2;n<=t;n++) {
flag[r.intValue()-1] = flag[r.intValue()-1] | (1<<n);
}
}
}
}
}
int count = 0;
for (int i=2;i<=max;i++) {
rs[i-1] = max-1;
for (int t=Integer.lowestOneBit(flag[i-1]);t!=0;t=Integer.lowestOneBit(flag[i-1])) {
rs[i-1]--;
flag[i-1] = flag[i-1]^t;
}
count+= rs[i-1];
}
System.out.println(count);
import java.util.LinkedList;
import java.util.List;
public class Test {
public int cf(int m,int n){
int temp=m;
for(int i=1;i<n;i++){
temp*=m;
}
return temp;
}
public void js(int min,int max){
int line=0;
for(int i=1;i<max;i++){
if(cf(min,i)>max){line=i-1;break;}
}
int count[]=new int[line];
int value[]=new int[line];
List<Integer> list=new LinkedList<Integer>();
for(int i=min;i<=Math.sqrt(max);i++){
if(list.contains(i)) continue;
list.add(i);
int temp=i;
for(int j=1;j<line;j++){
temp*=i;
if(temp<=max){
list.add(temp);
count[j]++;
}
}
}
count[0]=max-min+1;
value[0]=max-min+1;
for(int i=1;i<line;i++){
count[0]-=count[i];
value[i]=value[0]-max/(i+1)+min-1;
}
int num=0;
for(int i=0;i<line;i++){
num+=count[i]*value[i];
System.out.println("count: "+count[i]+"\tvalue: "+value[i]);
}
System.out.println("total :"+num);
}
public static void main(String args[]){
new Test().js(2,5);
long a=System.currentTimeMillis();
new Test().js(2,100);
long b=System.currentTimeMillis();
System.out.println("used: "+(b-a));
}
}
count: 3 value: 4
count: 1 value: 3
total :15
count: 87 value: 99
count: 6 value: 50
count: 2 value: 67
count: 2 value: 75
count: 1 value: 80
count: 1 value: 84
total :9361
used: 0
修改了下，最后结果是9277 final int max = 100;
int[][] flag = new int[max][max/4+1];
int count = (max-1)*(max-1);
BigInteger bm = BigInteger.valueOf(max);
for (int i=2;i<=max;i++) {
for (int j=2;j<=max;j++) {
int fm = j/4;
int f = j%4;
BigInteger b = BigInteger.valueOf(i);
BigInteger r = b.pow(j);
if (r.max(bm)==bm) {
if ((flag[i-1][fm]&f)!=f) {
int t = max/j;
for (int n=2;n<=t;n++) {
int fi = n/4;
int fg = 1<<(n%4);
int fff = flag[r.intValue()-1][fi];
if (fg!=(fg&fff)) {
flag[r.intValue()-1][fi] = fff | fg;
count--;
}
}
}
}
else {
break;
}
}
}
System.out.println(count);
对数字进行分类比如2-100
2, 4, 8,16,32,64
3，9,27,81
5,25
6,36
7,49
10,100
11
12
...
定义数组长度就是6，count代表个数，value代表的是不重复的值（比如第一列每个数的2-100次放均不重复，值就是100-2+1=99,第二列是第一列的2次方，求出第二列与第一列不重复的值，依次类推）
Math.pow(100, 100)也就E200
int[][] counters = new int[size+1][size+1];
/** Creates a new instance of DistinctPowers */
public DistinctPowers() {
}
private boolean lowerDivisorExists(int j, int f){
for (int c = 1; c < f; c++){
if (j%c == 0 && j/c <= size) return true;
}
return false;
}
public int getAnswer(){
for (int i = 2; i<=size; i++)
for (int j = 2; j <= size; j++)
counters[i][j] = 1;
for (int i = 2; i<=size; i++){
int power = i*i; //power == i^f
int limit = size;
for (int f=2; power <= size; f++){
for (int j = 2; j<= limit; j++){
if (j%f == 0){
int d = j/f;
if (d<=size && lowerDivisorExists(j, f) ){
counters[power][d] = 0;
}
}
}
limit = size*f;
power *= i;
}
}
int sum = 0;
for (int i = 2; i<=size; i++)
for (int j = 2; j<= size; j++)
sum += counters[i][j];
return sum;
}
public static void main(String[] args){
DistinctPowers dp = new DistinctPowers();
long start = System.currentTimeMillis();
System.out.println("Answer: " + dp.getAnswer());
long stop = System.currentTimeMillis();
System.out.println("Time used: " + (stop-start) + "ms");
}
import java.util.List;
public class Test {
public int cf(int m,int n){
int temp=m;
for(int i=1;i<n;i++){
temp*=m;
}
return temp;
}
public void js(int min,int max){
int line=0;
for(int i=1;i<max;i++){
if(cf(min,i)>max){line=i-1;break;}
}
int count[]=new int[line];
int value[]=new int[line];
List<Integer> list=new LinkedList<Integer>();
for(int i=min;i<=Math.sqrt(max);i++){
if(list.contains(i)) continue;
list.add(i);
int temp=i;
for(int j=1;j<line;j++){
temp*=i;
if(temp<=max){
list.add(temp);
count[j]++;
}
}
}
count[0]=max-min+1;
int a[][]=new int[line][max-min+1];
List<Integer> list1=new LinkedList<Integer>();
for(int i=1;i<=line;i++){
for(int j=min;j<=max;j++){
a[i-1][j-min]=(i)*j;
}
}
for(int i=0;i<line;i++){
for(int j=0;j<max-min+1;j++){
if(list1.contains(a[i][j])){continue;}
list1.add(a[i][j]);
value[i]++;
}
}
//System.out.println(list1);
for(int i=1;i<line;i++){
count[0]-=count[i];
}
int num=0;
for(int i=0;i<line;i++){
num+=count[i]*value[i];
System.out.println("count: "+count[i]+"\tvalue: "+value[i]);
}
System.out.println("total :"+num);
}
public static void main(String args[]){
new Test().js(2,5);
long a=System.currentTimeMillis();
new Test().js(2,100);
long b=System.currentTimeMillis();
System.out.println("used: "+(b-a));
}
}count: 3 value: 4
count: 1 value: 3
total :15
count: 87 value: 99
count: 6 value: 50
count: 2 value: 50
count: 2 value: 41
count: 1 value: 51
count: 1 value: 37
total :9183
used: 5
比如说此题中11,12,13,14,15的n次方均不重复
所以只需从数列中找出同底数的数，只需从2到sqrt(max)进行归类
int[] aLimit = {
2, 100
};
int[] bLimit = {
2, 100
};
int total = (aLimit[1] - aLimit[0] + 1) * (bLimit[1] - bLimit[0] + 1);
for (int a = aLimit[0]; a <= aLimit[1]; a++) {
int x = (int) Math.pow(a, bLimit[0]);
for (int b = bLimit[0]; b <= bLimit[1]; b++) {
if (x > bLimit[1]) {
break;
}
if (x >= aLimit[0] && x <= aLimit[1]) {
for (int n = bLimit[0]; b * n <= bLimit[1]; n++) {
total--;
System.out.printf("%d^%d=%d^%d%n", x, n, a, b*n);
}
}
x *= x;
}
}
System.out.println(total);
}更简单的解法
for (int i = 2; i <= 100; i++) {
for (int j = 1; j <= 100/2; j *= 2) {
total--;
}
} for (int i = 3; i <= 100; i *= 2) {
for (int k = 1; k <= 100/2/2; k *= 3) {
total--;
}
}
for (int i = 4; i <= 100; i *= 3) {
for (int k = 1; k <= 100/2/2/2; k *= 4) {
total--;
}
}
System.out.println(total);上面贴成坦克的了，这个思路还是用坦克的那个搞出来的，明天贴原理，看对不对
楼主点名，岂有不答的，给出我对坦克哥算法的看法(坦克哥，我对你可并没有什么意见)：其实32楼说了，这个少1只是个偶然罢了；坦克哥依据的公式是这个:(a^n)^m=a^(n*m)；
如(2^2)^2 = 2^(2*2)，
即：4^2 = 2^4；
这当然是正确的，但出错是在剔除重复数字的算法上；举一个反例(证明上常用的方法)：如：2^12 = 4^6 = 8^4 = 16^3 = 64^2 ；这也是数字4096的全部，也即需移除4个即可；
显然在a=2时，就已经删除了4次，即b=2、3、4、6时；
可是算法还会计算a=4时：4^6 = 16^3 = 64^2；在此处就会出现多删除现象了，多删除了2次；
计算a=8时：8^4 = 64^2；在此处多删除了1次；
也即会出现多删除3次；由上可知，结果中必然有重复数字；这样多删除的次数和本应删除却没有删除的次数抵消碰巧少个1。
另外，我觉得这个问题用set去穷举就没意思了，又不是考试，开拓思路才是我们的目的
结合这个思路，写出了下面的算法：import java.util.HashMap;public class TestQuestion3 {
private Point[] nums;
private int max;
public TestQuestion3(int max) {
this.max = max;
nums = new Point[max+1];
for (int i=2;i<=max;i++) {
nums[i] = new Point(i);
}
}
public void answer() {
for (int i=2;i<=max;i++) {
int m = nums[i].pv[0];
int n = nums[i].pv[1];
for (int j=2;j<=max;j++) {
if (Math.pow(i, j)<=max) {
int v = (int)Math.pow(i, j);
nums[v].setPow(new int[]{i,j});
}
nums[m].regist(n*j);
}
}
int count = (max-1)*(max-1);
int sm = (int)Math.sqrt(max);
for (int i=2;i<=sm;i++) {
count -= nums[i].repeatTimes;
}
System.out.println(count);
}
public static void main(String[] args) {
long start = System.currentTimeMillis();
TestQuestion3 q = new TestQuestion3(100);
q.answer();
System.out.println(System.currentTimeMillis()-start);
} class Point {
int value;
private int[] pv=new int[2];
private int repeatTimes=0;
private HashMap<Integer, Object> keys = new HashMap<Integer, Object>();
public Point(int value) {
this.value = value;
pv[0] = this.value;
pv[1] = 1;
}
public void setPow(int[] v) {
if (v[0]<pv[0]) {
pv[0] = v[0];
pv[1] = v[1];
}
}
public void regist(int p) {
if (keys.containsKey(p)) {
repeatTimes++;
}
else {
keys.put(p, null);
}
}
public int getRepeatTimes() {
return repeatTimes;
}
}
}
一个就是2楼最开始说的，用set穷举
另一个就是排除了，但关键就是，怎么保证排除的不多也不少
我在基础上完善，大致的思路就是
假设a=b^c，那么，a^d=b^(c*d)
然后通知b，它的(c*d)指数也是允许的，即使c*d>max，当有重复的通知过来的时候，重复次数加1
因为需要接收通知，所以将数字封装成Point对象
然后int[] pv记录得到这个数的最小底数以及指数，这样能保证每次通知都会被通知到最小底数上最后统计重复次数，由于有重复的底数只可能在2-sqrt(max)之间，所以，只需要用总数减去这部分底数的重复次数，就可以得到最终结果了
这题是有n*log(n)的方法的。简单处理的话，开一个n*log(n)的set也是不错的。
{
class Program
{
public static void Main()
{
int startA = 2, endA = 100;
int startB = 2, endB = 100; int log = (int)Math.Log(endA, 2);
bool[] counterFlag = new bool[endB * (log + 1)];
int[] rowCounter = new int[log]; for (int i = 1; i <= log; i++)
{
int count = 0; for (int j = startB; j <= endB; j++)
{
if (!counterFlag[i * j])
{
count++;
counterFlag[i * j] = true;
}
} rowCounter[i - 1] = count;
} int[] numFlag = new int[endA + 1]; for (int i = startA; i <= endA; i++)
{
if (numFlag[i] != 0)
continue; int num = i;
int power = 1; while (num <= endA)
{
numFlag[num] = power;
power++;
num *= i;
}
} int totalCount = 0; for (int i = startA; i <= endA; i++)
totalCount += rowCounter[numFlag[i] - 1]; Console.WriteLine(totalCount);
Console.ReadKey();
}
}
}
不知道是否还有什么问题
using System;namespace CSharpTest
{
class Program
{
public static void Main()
{
int startA = 5, endA = 100;
int startB = 2, endB = 100; int log = (int)Math.Log(endA, 2);
int[][] rowCounter = new int[log][]; for (int k = 0; k < log; k++)
{
bool[] counterFlag = new bool[endB * (log + 1)];
rowCounter[k] = new int[log]; for (int i = k + 1; i <= log; i++)
{
int count = 0; for (int j = startB; j <= endB; j++)
{
if (!counterFlag[i * j])
{
count++;
counterFlag[i * j] = true;
}
} rowCounter[k][i - 1] = count;
}
} int[] numFlag = new int[endA + 1];
int[] startFlag = new int[endA + 1]; for (int i = 2; i <= endA; i++)
{
if (numFlag[i] != 0)
continue; int num = i;
int power = 1; while (num <= endA)
{
if (num < startA)
startFlag[num]++; numFlag[num] = power;
power++;
num *= i;
}
} int totalCount = 0; for (int i = startA; i <= endA; i++)
totalCount += rowCounter[startFlag[i]][numFlag[i] - 1]; Console.WriteLine(totalCount);
Console.ReadKey();
}
}
}
2. 在for循环中如果一个数不能分解，则加1，如果能分解，则N<=边界，则重复，不加
public static void Solve01()
{
int log = (int)Math.Log(EndA, 2);
int[][] rowCounter = new int[log][]; for (int k = 0; k < log; k++)
{
bool[] counterFlag = new bool[EndB * (log + 1)];
rowCounter[k] = new int[log]; for (int i = k + 1; i <= log; i++)
{
int count = 0; for (int j = StartB; j <= EndB; j++)
{
if (!counterFlag[i * j])
{
count++;
counterFlag[i * j] = true;
}
} rowCounter[k][i - 1] = count;
}
} int[] numFlag = new int[EndA + 1];
int[] startFlag = new int[EndA + 1]; for (int i = 2; i <= EndA; i++)
{
if (numFlag[i] != 0)
continue; int num = i;
int power = 1;
int startNum = 0; while (num <= EndA)
{
if (num < StartA)
startNum++; startFlag[num] = startNum;
numFlag[num] = power;
power++;
num *= i;
}
} int totalCount = 0; for (int i = StartA; i <= EndA; i++)
totalCount += rowCounter[startFlag[i]][numFlag[i] - 1]; Console.WriteLine(totalCount);
Console.ReadKey();
}