牛客第五场 G max 思维-白红宇

牛客第五场 G max 思维

阅读量：7139 次

发布时间：2019-06-28

本文共 1335 字，大约阅读时间需要 4 分钟。

链接：

来源：牛客网

Give two positive integer c, n. You need to find a pair of integer (a,b) satisfy 1<=a,b<=n and the greatest common division of a and b is c.And you need to maximize the product of a and b

输入描述:

The first line has two positive integer c,n

输出描述:

Output the maximum product of a and b. If there are no such a and b, just output -1

示例1

输入

2 4

输出

说明

a=2,b=4

备注:

1<=c,n<=10^9 题意：给你两个数c，n，问你1-n之间最大的两个最大公约数是c的数的乘积 分析：分三种情况考虑： 　　　　当c大于n时，n以内没有能够整除c的数，明显答案是-1， 　　　　当n整除c的结果为1时，明显n以内的c可以整除c，此时答案是c*c 　　　　因为要找最大公约数是c的两个数，所以这些数肯定要能整除c，考虑先除以c，则剩下的数都是1-n范围内能整除c的，由于这两个数的最大公约数必须是c，所以他们必须互质。 　　　　到此我们要找的就是除以c后最大的两个互质数，因为n与n-1互质，所以此时的答案就是除以n后最大的数和比他小于1的数的乘积 AC代码：

#include #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #define ls (r<<1)#define rs (r<<1|1)#define debug(a) cout << #a << " " << a << endlusing namespace std;typedef long long ll;const ll maxn = 1e5 + 10;const ll mod = 1e9 + 7;int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); ll c, n; while( cin >> c >> n ) { if( n/c < 1 ) { cout << -1 << endl; } else if( n/c == 1 ) { cout << c*c << endl; } else { cout << (n/c-1)*(n/c)*c*c << endl; } } return 0;}