NC13890. HGCD
描述
long long gcd(long long a, long long b){ while(a > 0 && b > 0){ a %= b; swap(a , b); } return a + b; } long long hgcd(long long a, long long b) { while (a > 0 && b > 0) { a -= b; swap(a , b); } return a + b; } void swap(long long &a, long long &b){ long long t = a; a = b; b = t; } 输入描述
The first line of input will contain an integer T(1≤T≤5),denoting the number of test cases. For each test case: The first and only line contains an integer n (1≤n≤1012)
输出描述
For every test case output the number of times gcd(a,b)==hgcd(a,b) It's guaranteed that long long is enough for this problem.
示例1
输入:
2 3 2
输出:
8 4
说明:
In the first example, we have gcd(a,b)==hgcd(a,b) for all 1≤a≤3,1≤b≤3 except a=2,b=3)C++11(clang++ 3.9) 解法, 执行用时: 5849ms, 内存消耗: 492K, 提交时间: 2020-04-15 21:36:48
#include<iostream>
#include<cstdio>
#include<math.h>
using namespace std;
int T;
long long n,ans;
long long f[1200];
void calcfib()
{
f[1]=1ll;
f[2]=1ll;
for(int i = 3 ; i <= 60 ; ++i) f[i] = f[i-1] + f[i-2];
// ,printf("%lld %lld\n",i,f[i]);
}
void calc1()
{
long long sq = sqrt(n);
for(int i = 1;i <= sq ; ++ i)
ans += n / i;
long long l , r;
for(int i = 1 ; i <= sq; ++i)
{
l = (n/(i+1))+1;
if (l <= sq) continue;
// l = max(l,sq+1);
r = n/i;
ans += (r - l + 1) * i ;
}
}
void calc2()
{
long long sq = sqrt(n);
for (int j = 1; j <= 31;++j)
{
for(int k = 1;k * f[j] + f[j + 1] <= sq; ++k)
{
ans += n/(k * f[j] + f[j + 1]);
}
}
long long l,r,kl,kr;
for (int j = 1; j <= 31;++j)
{
for(int i = 1 ; i <= sq; ++i)
{
l = (n/(i+1ll))+1ll;
// if (l <= sq) continue;
l = max(l,sq+1);
r = n/i;
// if (r-f[j+1] <= 0ll || l-f[j+1]-1ll <= 0ll) continue;
kr = (r-f[j+1])/f[j];
kl = (l-f[j+1]-1ll)/f[j]+1ll;
if (kr < 1ll || kl < 1ll) continue;
ans += (kr-kl+1) * i ;
}
}
for (int j = 32; j <= 59;++j)
{
for(int k = 1 ;k * f[j] + f[j+1] <=n ; ++k)
{
ans += n/(k * f[j] + f[j+1]) ;
}
}
}
int main()
{
// freopen("dui.out","r",stdin);
scanf("%d",&T);
calcfib();
for(int i = 1 ;i <= T; ++i)
{
ans = 0ll;
scanf("%lld",&n);
if(n == 3) {
ans = 8ll,printf("%lld\n",ans);
continue;
}
calc1();//计算i < j的部分
calc2();//计算i > j的部分
printf("%lld\n",ans);
}
// fclose(stdin);
return 0;
}
C++(g++ 7.5.0) 解法, 执行用时: 4343ms, 内存消耗: 408K, 提交时间: 2022-09-24 19:32:31
#include<iostream>
#include<cstdio>
#include<math.h>
using namespace std;
int T;
long long n,ans;
long long f[1200];
void calcfib()
{
f[1] = 1ll;
f[2] = 1ll;
for(int i = 3 ; i <= 60 ; ++i) f[i] = f[i-1] + f[i-2];
}
void calc1()
{
long long sq = sqrt(n);
for(int i = 1;i <= sq ; ++ i)
ans += n / i;
long long l , r;
for(int i = 1 ; i <= sq; ++i)
{
l = (n/(i+1))+1;
if (l <= sq) continue;
// l = max(l,sq+1);
r = n/i;
ans += (r - l + 1) * i ;
}
}
void calc2()
{
long long sq = sqrt(n);
for (int j = 1; j <= 31;++j)
{
for(int k = 1;k * f[j] + f[j + 1] <= sq; ++k)
{
ans += n/(k * f[j] + f[j + 1]);
}
}
long long l,r,kl,kr;
for (int j = 1; j <= 31;++j)
{
for(int i = 1 ; i <= sq; ++i)
{
l = (n/(i+1ll))+1ll;
// if (l <= sq) continue;
l = max(l,sq+1);
r = n/i;
// if (r-f[j+1] <= 0ll || l-f[j+1]-1ll <= 0ll) continue;
kr = (r-f[j+1])/f[j];
kl = (l-f[j+1]-1ll)/f[j]+1ll;
if (kr < 1ll || kl < 1ll) continue;
ans += (kr-kl+1) * i ;
}
}
for (int j = 32; j <= 59;++j)
{
for(int k = 1 ;k * f[j] + f[j+1] <=n ; ++k)
{
ans += n/(k * f[j] + f[j+1]) ;
}
}
}
int main()
{
// freopen("dui.out","r",stdin);
scanf("%d",&T);
calcfib();
for(int i = 1 ;i <= T; ++i)
{
ans = 0ll;
scanf("%lld",&n);
if(n == 3) {
ans = 8ll,printf("%lld\n",ans);
continue;
}
calc1();//计算i < j的部分
calc2();//计算i > j的部分
printf("%lld\n",ans);
}
// fclose(stdin);
return 0;
}