首页 > 试题广场 >

求幂

[编程题]求幂

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

东东对幂运算很感兴趣,在学习的过程中东东发现了一些有趣的性质: 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 个满足要求的式子

数据范围： $1 \le n \le 10^6\$ ，答案对 $10^9+7 \$ 取模

输入描述:

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

输出描述:

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

示例1

输入

输出

算法知识视频讲解

C/C++

赵雨浓

// diL 等式左值底数， diL 等式右值底数
// ciL 等式左值次数， ciR 等式右值次数
// 1-n的数每一个数i都对应着一堆以之为底的1-n的数，有di = i^ci
// 对于每一个数，分两种情况：
// 1.diL==diR，这种情况共有n*n (对应1)+n*(n-1) (对应2-n)种情况
// 2.diL != diR, 遍历左右值即可，对于一对diL,diR有n / (ciR / (ciR和ciL的公约数)) * 2种情况
// 这里n / (ciR / (ciR和ciL的公约数))求的是i在1-n范围时，i ciL/ciR为正整数的个数,
// 这里对于ciR的所有因子，一部分由ciL(也就是二者的最大公约数)提供，一部分由i提供。
// long long 大法好！
#include <bits/stdc++.h>

using namespace std;
const int mod = 1e9+7;


unsigned int gcd(unsigned int i, unsigned j) {
    unsigned int res = j % i;
    while(res) {
        j = i;
        i = res;
        res = j % i;    
    }
    return i;
}

int main() {
    unsigned long long n;
    cin >> n;

    set<unsigned long long> sDis;

    unsigned int index = 2;
    unsigned long long count = (n * (n - 1) + n * n) % mod;
    while(index * index <= n) {

        unsigned long long diL = index;
        if(sDis.find(diL) != sDis.end()) {
            index++;
            continue;
        }

        unsigned long long tmp = index;
        while(tmp <= n) {
            sDis.insert(tmp);
            tmp *= index;
        }

        unsigned int ciL = 1;
        while(diL <= n) {
            unsigned ciR = ciL + 1;
            unsigned diR = diL * index;
            while(diR <= n) {
                count = (count + (n / (ciR / gcd(ciL,ciR)) * 2)) % mod;    
                ciR++;
                diR = diR * index;
            }
            ciL++;
            diL = diL * index;
        }
        index++;
    }
    cout << count <<endl;
}

发表于 2019-02-27 17:04:50 回复(4)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

const int M = 1e9+7;
typedef long long ll;

int main(){
    int n;
    scanf("%d", &n);
    ll s = (ll)n*(n*2-1)%M;
    set<int> S;
    for(int i=2;i*i<=n;i++){
        if(S.find(i)!=S.end())
            continue;
        int cnt=0, k=i;
        while(k<=n){
            S.insert(k);
            k *= i;
            cnt++;
        }
        for(k=1;k<=cnt;k++)
            for(int j=k+1;j<=cnt;j++)
                s = (s + n/(j/__gcd(k,j))*2) % M;
    }
    printf("%lld\n", s);
    return 0;
}

发表于 2020-10-07 11:39:30 回复(0)

C/C++

记号à

/*
 对于每一个数，分两种情况：
 1.a==c，这种情况共有n*n (对应1)+n*(n-1) (对应2-n)种情况，就是a,c底数为1时，有n*n种情况；a==c且不等于1时有n-1种（2～n），bd相等的情况有n种（1～n）。
2.a != c, 遍历左右值即可，对于一对a,c有n / (x和y中的较大值/ (x和y的公约数)) * 2种情况
 a^b=c^d----->(i^x)^b = (i^y)^d
 遍历i，且i^x<=n、j^y<=n,求出x和y的范围，除去底数相同的情况，i*i必定小于n
 遍历x和y，取出x和y的最大公约数放到底数做i的指数，(i^m)^n1*b = (i^m)^n2*d
 转换成求n1*b==n2*d 有多少种情况，
 x和y的最大值除以最大公约数m假设为n1，b/d=n2/n1,求有多少的b/d使得等式成立，n1>n2，b、d<n
 所以构造d为n1的倍数即可，总的倍数有n/n1个。同时等式两边可以对调，因此*2
*/
#include<iostream>
#include<set>
using namespace std;
int MOD = 1000000000 + 7;
int gcd(int a,int b){
    return (a % b == 0) ? b : gcd(b,a%b);
}
int main() {
    int n;
    cin>>n;
    //int会越界，且还需要强制类型转换
    long long ans =(long long) 1*n*(n*2-1) % MOD;
    set<int> s;
    //遍历i,因为去除了底数相同的情况,所以底数不等的情况下：底数必定大于1，次方必定大于1——>底数小于n的开方
    for (int i = 2; i*i <= n; i++){
        if (s.find(i)!=s.end()) continue;
        int tmp = i;
        int cnt = 0;
        //满足条件的底数，同时求x和y的范围
        while(tmp <= n) {
            s.insert(tmp);
            tmp = tmp * i;
            cnt++;
        }
        //相同的公约数，放到下面，反正不会大于n
        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;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

编辑于 2019-09-10 00:41:12 回复(2)

张博16

好难啊

发表于 2018-10-15 14:30:26 回复(0)

Python

逾清风

#算法复杂度过大

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 int(math.pow(i**j,1.0/k)) in range(1,n+1) and int(math.pow(i**j,1.0/k)) == math.pow(i**j,1.0/k):
count=count+1
print(count)

发表于 2018-09-09 14:16:38 回复(0)

zzz——ddd

#include<iostream>
#include<cmath>
using namespace std;
int gcd(int a,int b)//求公约数
{ int c;
c=(a>b)?b:a;
while(a%c!=0||b%c!=0)
{ c--;
}
return c;
}
int geshu(int a,int b,int n){//求最多组合数
int c=gcd(a,b);
return floor(n/(b/c));
}
long long fun(int i,int n){//求以i为底，在n里面有多少个次幂，1,2,3,4.。k然后任意两个不同的组合，
int k = 2;
int temp = i*i;
while (temp*i <= n){
temp *= i;
k++;
}
long long ans=0;
for(int j=1;j<k;j++){
for(int l=j+1;l<=k;l++){
ans+=geshu(j,l,n);
ans%=1000000007;
}

}
return ans;
}
bool zhishu(int i){//判断i是否是2-i里面中某个数的k次幂，n最大10的6次方，i最大10的三次方，即最大2的10次方
int k = sqrt(i);
for (int j = k; j >=2; j--){
if (i%j == 0){
int temp = i;
while (temp != 1 && temp%j == 0){
temp /= j;
}
if (temp == 1){
return true;
}
}
}
return false;
}
int main(){
long long n;
cin>>n;
long long ans=0;
ans+=n*(2*n-1);//以1位底的互相组合n*n，两边相同的n*(n-1)
ans%=1000000007;
for(int i=2;i<n;i++){//求非1为底，两边不相同的组合。
if(i*i>n){//停止条件
break;
}
if(!zhishu(i)){//不是1-（i-1）的某个数的幂次就运行fun函数，计算种类数
ans+=2*fun(i,n);//函数没有调转，所以*2
}
ans%=1000000007;
}

cout<<ans;
}

编辑于 2018-08-24 15:18:42 回复(7)

一个帅气潇洒的豆子

//尚未优化，主要用到快速幂
#include <iostream>

long long pow(int a, int b){
    long long curr = a,ans = 1, last;
    while (b){
        if(b%2)    ans *= curr;
        curr *= curr;
        b /= 2;
    }
    return ans;
}
int main(){
    int a = 1;
    long long n = 282;
    long long all = 0;

        while (a <= n){
            int b =1 ;
            while (b <= n){
                int c =1 ;

                while (c <= n){
                    int d =1;
                    while (d <= n){
                        if (pow(a, b) == pow(c, d)){
                            all++;

                        }
                        d++;
                    }
                    c++;
                }
                b++;
            }
            a++;
        }

    std::cout << all << std::endl;

    return 0;
}

编辑于 2018-05-23 11:55:36 回复(1)