1.【数论】给你N，求不大于N的最大完全平方数。

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;i++)
#define DOR(i,a,b) for(int i=(a),_b=(b);i>=_b;i--)
using namespace std;
#define ll long long
ll n;
ll ans;
int main(){
    scanf("%lld",&n);
        ll a=sqrt(n);//n=100 a=10 n=10 a=3
        printf("%lld\n",a*a);
    return 0;
}
数论

2.

题目描述

多次查询[l,r]范围内的完全平方数个数

定义整数x为完全平方数当且仅当可以找到整数y使得y*y=x

输入描述:

第一行一个数n表示查询次数
之后n行每行两个数l,r

输出描述:

对于每个查询，输出一个数表示答案
示例1

输入

5
1 3
1 4
2 4
4 4
1 1000000000

输出

1
2
1
1
31622

备注:

n <= 100000
0<= l <= r <= 1000000000
【代码】：
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;i++)
#define DOR(i,a,b) for(int i=(a),_b=(b);i>=_b;i--)
#define ll long long
using namespace std;
 
int n;
 
int main(){
    cin>>n;
    FOR(i,1,n){
        int L,R;
        scanf("%d%d",&L,&R);
        int a=sqrt(L),b=sqrt(R);
        if(a*a==L)a--;
        printf("%d\n",b-a);
    }
    return 0;
}
完全平方数

 

3.【数论】：

求 1 到 n 的所有数的约数和

暴力方法就是枚举每个数，算出他的约数和即可，这样有点慢。

另一种思路，枚举约数，判断他是谁的约数，并记录（即他的倍数有多少个），在乘以他自己。

n/i求的是n以内，i的倍数有多少个，在乘以i即可。

可以发现，枚举到n/2时，往后的所有数的倍数只有他自己，n/i = 1（i>n/2），这里可以用数学方法算出。

代码：

#include<cstdio>

int main()
{
    int n,ans = 0;
    scanf("%d",&n);
    
    for (int i=1; i<=n; ++i)
    {
        ans += (n/i)*i;
    }
    
    printf("%d",ans);
    
    return 0;
}

 

【类似】：

题目描述

给个n，求1到n的所有数的约数个数的和~

输入描述:

第一行一个正整数n

输出描述:

输出一个整数，表示答案
示例1

输入

3

输出

5

说明

样例解释：
1有1个约数1
2有2个约数1,2
3有2个约数1,3

备注:

n <= 100000000
【代码】：
#include<cstdio>  
using namespace std;  
typedef long long LL;  
int main ()  
{  
    int n;  
    LL ans=0;  
    scanf("%d",&n);  
    for(int i=1;i<=n;i++)  
        ans+=n/i;  
    printf("%lld\n",ans);  
    return 0;  
}