P3764 签到题 III

    • 36通过
    • 222提交
  • 题目提供者 fjzzq2002
  • 评测方式 云端评测
  • 标签 洛谷原创 O2优化 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    pj组选手zzq近日学会了求最大公约数的辗转相除法。

    题目描述

    类比辗转相除法,zzq定义了一个奇怪的函数:

    typedef long long ll;
    ll f(ll a,ll b)
    {
        if(a==b) return 0;
        if(a>b) return f(a-b,b+b)+1;
        else return f(a+a,b-a)+1;
    }

    zzq定义完这个函数兴高采烈,随便输入了两个数,打算计算f值,发现这个函数死循环了...于是zzq定义这个函数递归死循环的情况下f值为0。

    现在zzq输入了一个数n,想要求出$\sum_{i=1}^n \sum_{j=1}^n f(i,j)$ 。

    输入输出格式

    输入格式:

    一行两个数n。

    输出格式:

    一行一个数$\sum_{i=1}^n \sum_{j=1}^n f(i,j)$ 。

    输入输出样例

    输入样例#1: 复制
    100
    输出样例#1: 复制
    1124
    输入样例#2: 复制
    2000
    输出样例#2: 复制
    68204

    说明

    对于10%的数据,$n \leq 300$ 。

    对于40%的数据,$n \leq 2000$ 。

    对于70%的数据,$n \leq 5 \times 10^5$ 。

    对于100%的数据,$1 \leq n \leq 5 \times 10^{11}$ 。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。