给定两个数字w和m，我们需要确定是否有可能用w的幂来表示m。数字w的幂可以加或减得到m，并且w的每个幂只能使用一次。 例如：
null
Input : 3 7Output : YesAs 7 = 9 - 3 + 1 (3^2 - 3^1 + 3^0 )so it is possible .Input : 100 50Output : NoAs 50 is less than 100 so we can neverrepresent it in the powers of 100 .
在这里，我们必须用w的幂来表示m，只使用一次，所以可以通过下面的等式来表示。 c0+c1*w^1+c2*w^2+…=m–（方程式1） 其中每个c0，c1，c2…都是 -1 （减去w的幂）， 0 （不使用w的幂）， 1. （用于添加w的幂）。 =>c1*w^1+c2*w^2+…=m–c0 =>w（c1+c2*w^1+c3*w^2+…）=m–c0 =>c1+c2*w^1+c3*w^2+…=（m–c0）/w–（方程式2） 现在，注意等式1和等式2——我们试图再次解决相同的问题。所以我们必须递归到m>0。对于这样一个解的存在（m-ci）必须是w的倍数，其中ci是方程的系数。ci可以是-1、0、1。所以我们必须检查这三种可能性 （（m-1）%w==0），（（m+1）%w==0）和（m%w==0） .如果不是，那么就没有任何解决方案。
C++
// CPP program to check if m can be represented // as powers of w. #include <bits/stdc++.h> using namespace std; bool asPowerSum( int w, int m) { while (m) { if ((m - 1) % w == 0) m = (m - 1) / w; else if ((m + 1) % w == 0) m = (m + 1) / w; else if (m % w == 0) m = m / w; else break ; // None of 3 worked. } // If m is not zero means, it can't be // represented in terms of powers of w. return (m == 0); } // Driver code int main() { int w = 3, m = 7; if (asPowerSum(w, m)) cout << "Yes" << endl; else cout << "No" << endl; return 0; } |
JAVA
// Java program to check if m can // be represented as powers of w. class GFG { static boolean asPowerSum( int w, int m) { while (m > 0 ) { if ((m - 1 ) % w == 0 ) m = (m - 1 ) / w; else if ((m + 1 ) % w == 0 ) m = (m + 1 ) / w; else if (m % w == 0 ) m = m / w; else break ; // None of 3 worked. } // If m is not zero means, it can't be // represented in terms of powers of w. return (m == 0 ); } // Driver function public static void main (String[] args) { int w = 3 , m = 7 ; if (asPowerSum(w, m)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 program to check if m can # be represented as powers of w. def asPowerSum(w, m): while (m > 0 ): if ((m - 1 ) % w = = 0 ): m = (m - 1 ) / w; elif ((m + 1 ) % w = = 0 ): m = (m + 1 ) / w; elif (m % w = = 0 ): m = m / w; else : break ; # None of 3 worked. # If m is not zero means, it can't be # represented in terms of powers of w. return (m = = 0 ); # Driver code w = 3 ; m = 7 ; if (asPowerSum(w, m)): print ( "Yes" ); else : print ( "No" ); # This code is contributed by mits |
C#
// C# program to check if // m can be represented // as powers of w. using System; class GFG { static bool asPowerSum( int w, int m) { while (m > 0) { if ((m - 1) % w == 0) m = (m - 1) / w; else if ((m + 1) % w == 0) m = (m + 1) / w; else if (m % w == 0) m = m / w; else break ; // None of 3 worked. } // If m is not zero means, // it can't be represented // in terms of powers of w. return (m == 0); } // Driver Code static public void Main () { int w = 3, m = 7; if (asPowerSum(w, m)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed // by akt_mit. |
PHP
<?php // PHP program to check if m can // be represented as powers of w. function asPowerSum( $w , $m ) { while ( $m ) { if (( $m - 1) % $w == 0) $m = ( $m - 1) / $w ; else if (( $m + 1) % $w == 0) $m = ( $m + 1) / $w ; else if ( $m % $w == 0) $m = $m / $w ; else break ; // None of 3 worked. } // If m is not zero means, it can't be // represented in terms of powers of w. return ( $m == 0); } // Driver code $w = 3; $m = 7; if (asPowerSum( $w , $m )) echo "Yes" ; else echo "No" ; // This code is contributed by mits ?> |
Javascript
<script> // Javascript program to check if m can // be represented as powers of w. function asPowerSum(w, m) { while (m > 0) { if ((m - 1) % w == 0) m = (m - 1) / w; else if ((m + 1) % w == 0) m = (m + 1) / w; else if (m % w == 0) m = m / w; else break ; // None of 3 worked. } // If m is not zero means, it can't be // represented in terms of powers of w. return (m == 0); } // Driver code let w = 3, m = 7; if (asPowerSum(w, m)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by sanjoy_62. </script> |
输出：
Yes
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
