给定一个数n，我们需要求a和b的有序对的个数，这样gcd（a，b）就是b本身 例如：
null
Input : n = 2Output : 3(1, 1) (2, 2) and (2, 1) Input : n = 3Output : 5(1, 1) (2, 2) (3, 3) (2, 1) and (3, 1)
天真的方法： gcd（a，b）=b意味着b是a的一个因子。因此，对的总数将等于每个a=1到n的除数之和。请参考 求一个自然数的所有除数 用于实施。 有效方法： gcd（a，b）=b意味着a是b的倍数。因此，对的总数将是每个b的倍数之和（其中b从1到n变化），其小于或等于n。 对于数字i，i的倍数小于或等于下限（n/i）。所以我们需要做的就是把每个i=1到n的下限（n/i）求和，然后打印出来。但是可以做更多的优化。对于i>=sqrt（n），地板（n/i）可以有大气2*sqrt（n）值。楼层（n/i）可以在1到sqrt（n）之间变化，类似地，对于i=1到sqrt（n），楼层（n/i）的值可以在1到sqrt（n）之间变化。2*sqrt（n）个不同值的总和
let floor(n/i) = kk <= n/i < k + 1n/k+1 < i <= n/kfloor(n/k+1) < i <= floor(n/k)Thus for given k the largest value of i for which the floor(n/i) = k is floor(n/k)and all the set of i for which the floor(n/i) = k are consecutive
CPP
// C++ implementation of counting pairs // such that gcd (a, b) = b #include <bits/stdc++.h> using namespace std; // returns number of valid pairs int CountPairs( int n) { // initialize k int k = n; // loop till imin <= n int imin = 1; // Initialize result int ans = 0; while (imin <= n) { // max i with given k floor(n/k) int imax = n / k; // adding k*(number of i with // floor(n/i) = k to ans ans += k * (imax - imin + 1); // set imin = imax + 1 and k = n/imin imin = imax + 1; k = n / imin; } return ans; } // Driver function int main() { cout << CountPairs(1) << endl; cout << CountPairs(2) << endl; cout << CountPairs(3) << endl; return 0; } |
JAVA
// Java implementation of counting pairs // such that gcd (a, b) = b class GFG { // returns number of valid pairs static int CountPairs( int n) { // initialize k int k = n; // loop till imin <= n int imin = 1 ; // Initialize result int ans = 0 ; while (imin <= n) { // max i with given k floor(n/k) int imax = n / k; // adding k*(number of i with // floor(n/i) = k to ans ans += k * (imax - imin + 1 ); // set imin = imax + 1 // and k = n/imin imin = imax + 1 ; k = n / imin; } return ans; } // Driver code public static void main(String[] args) { System.out.println(CountPairs( 1 )); System.out.println(CountPairs( 2 )); System.out.println(CountPairs( 3 )); } } // This code is contributed by Anant Agarwal. |
Python3
# Python implementation of counting # pairs such that gcd (a, b) = b # returns number of valid pairs def CountPairs(n): # initialize k k = n # loop till imin <= n imin = 1 # Initialize result ans = 0 while (imin < = n): # max i with given k floor(n / k) imax = n / k # adding k*(number of i with # floor(n / i) = k to ans ans + = k * (imax - imin + 1 ) # set imin = imax + 1 and # k = n / imin imin = imax + 1 k = n / imin return ans # Driver code print (CountPairs( 1 )) print (CountPairs( 2 )) print (CountPairs( 3 )) # This code is contributed by Anant Agarwal. |
C#
// C# implementation of counting // pairs such that gcd (a, b) = b using System; class GFG { // returns number of valid pairs static int CountPairs( int n) { // initialize k int k = n; // loop till imin <= n int imin = 1; // Initialize result int ans = 0; while (imin <= n) { // max i with given // k floor(n / k) int imax = n / k; // adding k * (number of i // with floor(n / i) = k // to ans ans += k * (imax - imin + 1); // set imin = imax + 1 // and k = n / imin imin = imax + 1; k = n / imin; } return ans; } // Driver code public static void Main(String []args) { Console.WriteLine(CountPairs(1)); Console.WriteLine(CountPairs(2)); Console.WriteLine(CountPairs(3)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP implementation of counting // pairs such that gcd (a, b) = b // returns number of valid pairs function CountPairs( $n ) { // initialize k $k = $n ; // loop till imin <= n $imin = 1; // Initialize result $ans = 0; while ( $imin <= $n ) { // max i with given k floor(n/k) $imax = $n / $k ; // adding k*(number of i with // floor(n/i) = k to ans $ans += $k * ( $imax - $imin + 1); // set imin = imax + 1 // and k = n/imin $imin = $imax + 1; $k = (int)( $n / $imin ); } return $ans ; } // Driver Code echo (CountPairs(1) . "" ); echo (CountPairs(2) . "" ); echo (CountPairs(3) . "" ); // This code is contributed by Ajit. ?> |
Javascript
<script> // Javascript implementation of counting pairs // such that gcd (a, b) = b // returns number of valid pairs function CountPairs(n) { // initialize k let k = n; // loop till imin <= n let imin = 1; // Initialize result let ans = 0; while (imin <= n) { // max i with given k floor(n/k) let imax = Math.floor(n / k); // adding k*(number of i with // floor(n/i) = k to ans ans += k * (imax - imin + 1); // set imin = imax + 1 and k = n/imin imin = imax + 1; k = Math.floor(n / imin); } return ans; } // Driver function document.write(CountPairs(1) + "<br>" ); document.write(CountPairs(2) + "<br>" ); document.write(CountPairs(3) + "<br>" ); // This is code is contributed by Mayank Tyagi </script> |
输出：
135
本文由 阿尤什·贾哈 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 贡献极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
