这个数N能否表示为若干个X的幂之和呢？

本文共计841个文字，预计阅读时间需要4分钟。

检查一个数N是否可以表示为X的平方和，原文如下：

检查一个数N是否可以表示为X的平方和：原文：https://www.geeksforgeeks.org/check-if-a-number-n-can-be-represented-as-sum-of-squares-of-x/简化后：检查N是否可表示为X的平方和

检查一个数N是否可以表示为X的幂之和原文:www . geesforgeks . org/check-if-a-number-n-可表示为-x-or-not 的幂之和/

给定两个正数 N 和 X ，任务是检查给定的数字 N 是否可以表示为XT9】的不同次幂之和。如果发现为真，则打印“是”，否则打印“否”。

例:

输入: N = 10，X = 3输出:是说明:给定值 N(= 10)可写成(1 + 9) = 3 ⁰ + 3 ² 。因为 X(= 3)的所有幂都是不同的。因此，打印“是”。

输入: N= 12，X = 4T5输出:**否

方法:给定的问题可以通过检查号 N 是否可以写成 base X 来解决。按照以下步骤解决问题:

• 迭代一个循环直到 N 的值至少为0并执行以下步骤:
  • 当 N 除以 X 时，计算余数 rem 的值。
  • 如果 rem 的值至少为2，则打印“否”并返回。
  • 否则，将 N 的值更新为 N / X 。
• 完成上述步骤后，如果不存在任何终止，则打印“是”，因为 N 处的结果可以用 X 的不同幂表示。

下面是上述方法的实现:

C++

// C++ program for the above approach#include using namespace std;// Function to check if the number N// can be expressed as the sum of// different powers of X or notbool ToCheckPowerofX(int n, int x){    // While n is a positive number    while (n > 0) {        // Find the remainder        int rem = n % x;        // If rem is at least 2, then        // representation is impossible        if (rem >= 2) {            return false;        }        // Divide the value of N by x        n = n / x;    }    return true;}// Driver Codeint main(){    int N = 10, X = 3;    if (ToCheckPowerofX(N, X)) {        cout << "Yes";    }    else {        cout << "No";    }    return 0;}

Java 语言(一种计算机语言，尤用于创建网站)

// Java program for the above approachimport java.io.*;import java.util.*;class GFG{// Function to check if the number N// can be expressed as the sum of// different powers of X or notstatic boolean ToCheckPowerofX(int n, int x){    // While n is a positive number    while (n > 0)    {        // Find the remainder        int rem = n % x;        // If rem is at least 2, then        // representation is impossible        if (rem >= 2)        {            return false;        }        // Divide the value of N by x        n = n / x;    }    return true;}// Driver Codepublic static void main (String[] args){    int N = 10, X = 3;    if (ToCheckPowerofX(N, X))    {        System.out.print("Yes");    }    else    {        System.out.print("No");    }}}// This code is contributed by sanjoy_62

Python 3

# Python3 program for the above approach# Function to check if the number N# can be expressed as the sum of# different powers of X or notdef ToCheckPowerofX(n, x):    # While n is a positive number    while (n > 0):        # Find the remainder        rem = n % x        # If rem is at least 2, then        # representation is impossible        if (rem >= 2):            return False        # Divide the value of N by x        n = n // x    return True# Driver Codeif __name__ == '__main__':    N = 10    X = 3    if (ToCheckPowerofX(N, X)):        print("Yes")    else:        print("No")# This code is contributed by bgangwar59

C

// C# program for the above approachusing System;class GFG{// Function to check if the number N// can be expressed as the sum of// different powers of X or notstatic bool ToCheckPowerofX(int n, int x){    // While n is a positive number    while (n > 0)    {        // Find the remainder        int rem = n % x;        // If rem is at least 2, then        // representation is impossible        if (rem >= 2)        {            return false;        }        // Divide the value of N by x        n = n / x;    }    return true;}// Driver codepublic static void Main(String []args){     int N = 10, X = 3;    if (ToCheckPowerofX(N, X))    {        Console.Write("Yes");    }    else    {        Console.Write("No");    }}}// This code is contributed by code_hunt,

java 描述语言

Output: 

Yes

时间复杂度: O(log N)辅助空间: O(1)