专栏首页个人学习总结做题总结——Fear Factoring

做题总结——Fear Factoring

做题总结——Fear Factoring

原题

题意分析:

这道题目题意很简单,就是求出[a,b]区间内所有数的因数之和

做题思路:

开始自己的做法是特别愚蠢的 暴力破解法,也就是分别枚举[a,b]区间里每一个数的因数,最后累加起来,可想而知这种做法肯定是不对的。后面听了学长的讲解,这道题一共有两种思路。

  • 枚举从1到sqrt(b)的每一个数i,求出[a,b]能够以i作为因数的最小的那个数,这样就可以得到[a,b]区间内所有可以以i为因数的数,再进行累加即可
  • 利用数论分块的方法,具体分析参考数论分块解决

代码实现

1、暴力破解法:

//利用暴力破解法
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long a, b, i;
    while (cin >> a >> b)
    {
        long long ans=0;
        for (i = 1; i * i <= b; i++)
        {
            long long d = (a / i) * i;    //求出[a,b]内第最小的能够以i作为因数的数
            while (d < a  || i*i>d)      //如果求出的d小于a或者原来已经求过因数了,取下一个能够以i为因数的(也就是d+i)
            {
            	d+=i;
            }
            for (d; d <= b; d += i)      //累加因数
            {
                ans += i;               
                if (i < d / i)          //这里的判断防止累加重复了
                {
                    ans += d / i;
                }
            }
        }
        cout << ans << endl;
    }
    //system("pause");
    return 0;
}

2、数论分块法

//利用数论分块的思想解决该问题
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;    //这里不用unsigned long long无法AC
ll sol(ll n)
{
    ll ans=0;
    ll r;
    for(ll l=1;l<=n;l=r+1)  //枚举因数,同时更新区间的右端点
    {
        ll s=n/l;  //s是从1到n中含因数l的数的个数
        r=n/s;   //[l,r]中的每一个数能作为从1到n中s个数的因数(相当于求分块区间的右端点)(这里描述不太准确,以后想明白再修改)
        ans+=(l+r)*(r-l+1)/2*s;     //[l,r]作为因数的贡献,相当于求一个等比数列的值
    }   
    return ans;
}
int main()
{
    ll a,b;
    while((scanf("%llu%llu", &a, &b)!=EOF))
    {
        cout<<sol(b)-sol(a-1)<<endl;
    }
    //system("pause");
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 线性Galois群在有限域上的多项式分解:加法组合方法(CS CC)

    让 F〜(X)∈ ž [ X] 学位-ñ 多项式 F(X):=F〜(X)mod p 分解为 ñ 超过线性因子 Fp。我们研究确定性分解的问题F(X) 过度 Fp...

    刘子蔚
  • 分解多维数据以创建复杂的贝叶斯分类器(CS)

    在本文中,我们导出了一个明确的公式,用于计算给定分类数据集的因式分解的边际可能性。由于边际可能性与因式分解的后验概率成正比,因此可以使用这些可能性对所有可能的因...

    Alfred_Yip
  • 做题总结——Delayed Work

    这道题目是来计算最低的支付金额,该金额由工人的工资和罚款两部分组成。根据题意描述可知,工资的表达式:MX,罚款的表达式:(KP)/M,因此总金额表达式:MX+(...

    用户8224910
  • 做题总结——Pawn’s Revenge

    这道题目自己一开始时也没有思路(后来才发现其实也并不难,实在是学的不太好),后来从网上查找了一些资料,大概明白了这道题目的思路。这道题目是在已经有且只有一个K棋...

    用户8224910
  • 做题总结—— Latin Squares

    题目就是输入一个二维数组(用来表示矩阵),判断对于矩阵中的每一个数字是否在该数字所在的行、所在的列的只出现一次(相当于数独的概念)。如果是的话,则该矩阵是拉丁方...

    用户8224910
  • 做题总结——中位数

    这道题目题意其实并不理解,相当于在插入数据的过程中动态求中位数,每当插入奇数个数据时就求这所有奇数个数据的中位数。

    用户8224910
  • 做题总结——造房子

    用户8224910
  • 笔记与随想 — 解决问题

    捷义
  • 做题总结——younik要排号

    这道题目理解起来不难,就相当于求younik之前有多少个不同的人,再加上一,就是younik是第几个被叫到的人。

    用户8224910
  • 做题总结——使徒袭来

    这道题目利用数学知识可以知道,当三个正整数的值相等时,三个数的和最小,相当于a=b=c=n^(1/3)时,(a+b+c) min=3*n ^(1/3),编写代码...

    用户8224910
  • 做题总结——虚空之力

    这道题目是求出一个字符串中能够挑选出对应字符从而组成指定字符串(“king” 或 “kinging”)的数量

    用户8224910
  • 做题总结——走出迷宫

    从起点开始,分别向上、下、左、右四个方向进行搜索,如果搜索到了终点,则说明能够到达终点;否则,将该点压入队列之中,继续进行下面的搜索,并将该点标记成已访问。

    用户8224910
  • 做题总结——数字三角形

    先介绍一种解法。这道题目可以利用“杨辉三角”的思路,根据一个上面的元素与下面两个元素的递推公式(在动态规划里面称作状态转移方程),从下至上地解决此问题(详细思路...

    用户8224910
  • 做题总结——牛牛爱博弈

    自己再网上看了一些题解,感觉还是没有弄明白这其中的原理,所以就不在这写了,关于数论中博弈原理的各种应用需要自己去进行学习,总之 结论就是当n%3==0时,则牛牛...

    用户8224910
  • 做题总结——小M和天平

    根据这道题给出的数据范围可以知道,利用所有的石头能够查询的物体质量是不会查过100*100=10000的,所以可以直接利用暴力枚举的方法进行求解。

    用户8224910
  • 做题总结——单词查找树

    这道题目就是一道Trie树相关操作的题目(这道题目只涉及了插入操作),求最少的结点数目就相当于输出向Trie树中插入的最后一个结点的序号(注意开始就有根结点)

    用户8224910
  • 你以为川普的推特都是他自己写的?数据可不这么认为!

    写在前面 近日,一直以“推特治国”闻名的川普正式宣誓就任了美国第 45 任总统。 川普这次在美国大选中胜出,他的推特也发挥了巨大的作用。相比大多数总统竞选人来说...

    CDA数据分析师
  • 做题总结——牛牛爱字符串

    这道题目题意比较好理解,就是输出所给字符串中含有的数字,对于有前导零的数字需要注意去掉前导零,同时注意如果只有一个数字0直接输出。

    用户8224910
  • ssh key类型这么多,要如何选择呢?

    用过ssh的朋友都知道,ssh key的类型有很多种,比如dsa、rsa、 ecdsa、ed25519等,那这么多种类型,我们要如何选择呢?

    KINGYT

扫码关注云+社区

领取腾讯云代金券