从“10-100能被3或5整除的数的和”想到的

Question

迭代统计整除算法重用

Answer 1

有bug，好伤心，果断是溢出的问题，应该是long和int的问题

Answer 2

把int和long都换成long long类型的，就没有问题了

Answer 3

我去，真是一个令人伤心的结果
//从“10-100能被3或5整除的数的和”想到的
//首先解决这个问题：
//简单的for循环真的简单不过了，算法时间复杂度为O（n-m）
//有没有更加快的，更加通用的算法？
//先抽象一下问题描述：
//求[m,n]中能被a或者b整除的数的和。
//1.先统计在[1，a*b]内有X1个值符合要求，应该放入result集合，和值为sum1；      O(a*b)
//2.扩展[m,n]到最相邻的公倍数区间[m1,n1]，其中m1%(a*b)==1，n1%(a*b)==0；      O(1)
//3.处理区间[m1,n1]，这是[1,a*b]的倍数集合：
//   0+[1,a*b]，a*b+[1,a*b],2*a*b+[1,a*b],...
//   设x2=(n1-m1)/h；为区间个数减1
//   求和：
//    sum=x1*h*(x2+1)*x2/2+sum1*(x2+1);         O(1)
//4.处理落单的离散值：{[m1,n1]-[m,n]}集合中的一些值（肯定少于2*a*b个值）:       小于O（2*a*b)
//  简单的用两小段for循环逐个判断，符合要求的值（能被a或者b整除的数）都要减去
//  （因为已经算进去第3步中的sum中了）：
//5.求得和值
// 算法总复杂度为O(a*b)#include <iostream>
#include<windows.h> 
using namespace std;long long mySum(long long m,long long n,long long a,long long b)
{
long long sum=0,sum1=0;
long long m1=0,n1=0,x1=0,x2=0;
long long h=a*b;
//第1步
for(long long i=1;i<=h;i++)
{
if(i%a==0 || i%b==0)
{
sum1+=i; x1++;
}
}
//第2步
m1=m-m%h+1;
if(n%h!=0) n1=n-n%h+h;
else n1=n;
//第3步
x2=(n1-m1)/h;
sum=(x1*h*(x2+1)*x2)/2+sum1*(x2+1);
//第4步
for(long long i=m1;i<=m-1;i++)
{
if(i%a==0 || i%b==0)
sum-=i;
}
for(long long i=n+1;i<=n1;i++)
{
if(i%a==0 || i%b==0)
sum-=i;
}
//第5步
return sum;
}
//普通for循环的算法
//算法时间复杂度为O（n-m）
long long simple(long long m,long long n,long long a,long long b)
{
long long result=0;
for(long long i=m;i<=n;++i)
{
if(i%a==0 || i%b==0)
result+=i;
}
return result;
}int main()
{
long long m,n,a,b;
while (cin>>m>>n>>a>>b)
{
DWORD start_time=GetTickCount(); 
cout<<"mySum:"<<mySum(m,n,a,b)<<endl;
DWORD end_time=GetTickCount();  
cout<<"The mySum run time is:"<<(end_time-start_time)<<"ms!"<<endl;//输出运行时间 start_time=GetTickCount();
cout<<"Simple:"<<simple(m,n,a,b)<<endl;
end_time=GetTickCount();  
cout<<"The Simple run time is:"<<(end_time-start_time)<<"ms!"<<endl;//输出运行时间 cout<<endl;
}
system("pause");
}

Answer 4

a = 0;
for(..)
a += 3
或 a += 5,返回的就是你要的结果

Answer 5

+1
之前已经有吧友给出了源码,原理就是定义一个sum(a),对a在m,n区间的等差数列求和
最终结果就是sum(a)+sum(b)-sum(a*b)

Answer 6

另外这是c#区,不要来秀你的语言,OK?虽然我不知道你那是什么玩意但是肯定不是c#警告一次.否则下次封号封IP

Answer 7

同意,不同语言只是语法不同,算法才是核心,是可以一起讨论的.
如果纠结于语法,那么到具体控件的使用上,winform,webform,wpf,wcf,都不一样,难道就没法一起玩了,还要单独开区分别讨论...

Answer 8

我平时都是用VS2005,.net2.0
你们整天讨论linq,lamada,task我是不是就不要再来了...

Answer 9

我只想说，虽然我是新手，而且我的确是在C#区发了一个用c++实现的不算优秀的算法，但是我意并不在代码，而是算法分析。即使一个完全不懂c++的人，只要会任何一种编程语言，他都可以用他熟悉的语言实现这个算法。
没错，你是大神，技术分超高，排名超前，但是你堂堂C#区的大神，居然对一小段简单的c++代码描述为“不知道那是什么玩意”，这真是太令人失望了！！对于我用c++代码实现，解释一下，那是因为我入门语言就是c++，用自己最习惯的编程语言实现一个算法，这是很正常的事情，虽然张贴在c#区的确不对，但并没有影响阅读，希望大家可以理解。

Answer 10

骚年们， 颤抖吧， 初等数论 + 编程， 就是这么风骚， 哈哈哈哈哈哈哈原理， 小步长对于大步长的余数，是循环递增的， 哦哈哈哈
            int differ = 2;
            int differ_in_process = -1;            for (int i = 3; i <= 100; i += 3)
            {
                differ_in_process = i % 5;                if (differ_in_process > differ)
                {
                    Console.WriteLine(i);
                }
                else if (differ_in_process < differ && differ_in_process != 0)
                {
                    Console.WriteLine("*{0}", i - differ_in_process);
                    Console.WriteLine(i);
                }
                else if (differ_in_process < differ && differ_in_process == 0)
                {
                    Console.WriteLine("*#{0}", i);
                }                differ = differ_in_process;
            }