2909: Number of Containers 

Time Limit(Common/Java):1000MS/3000MS     Memory Limit:65536KByte

Total Submit: 130            Accepted:64

Description

 

For two integers m and k, k is said to be a container of m if k is divisible by m. Given 2 positive integers n and m (m < n), the function f(n, m) is defined to be the number of containers of m which are also no greater than n. For example, f(5, 1)=4, f(8, 2)=3, f(7, 3)=1, f(5, 4)=0...

Let us define another function F(n) by the following equation: 

Now given a positive integer n, you are supposed to calculate the value of F(n).

 

Input

 

There are multiple test cases. The first line of input contains an integer T(T<=200) indicating the number of test cases. Then T test cases follow.

Each test case contains a positive integer n (0 < n <= 2000000000) in a single line.

 

Output

For each test case, output the result F(n) in a single line.

Sample Input

2

1

4

Sample Output

0

4

这个题目本质是求1-n的n/i，但是n很大，所以你很快就会发现某段的值是一定的

所以就可以把他搞出sqrt(n)段进行分步求解

#include
       
        #include
        
         using namespace std;#define lson l,(l+r)/2,rt<<1#define rson (l+r)/2+1,r,rt<<1|1#define dbg(x) cout<<#x<<" = "<< (x)<< endl#define pb push_back#define fi first#define se second#define ll long long#define sz(x) (int)(x).size()#define pll pair
         
          #define pii pair
          
           #define pq priority_queueconst int N=1e5+5,MD=1e9+7,INF=0x3f3f3f3f;const ll LL_INF=0x3f3f3f3f3f3f3f3f;const double eps=1e-9,e=exp(1),PI=acos(-1.);int a[N];int main(){    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);    int T;    cin>>T;    while(T--)    {        int n;        cin>>n;        ll sum=-n,r=sqrt(n+0.5);        for(int i=1;i<=r;i++)sum+=n/i;        for(int i=1;i<=r;i++)sum+=i*1LL*(n/i-n/(i+1));        if(r==n/r)sum-=r;        cout<
           
            <<"\n";    }    return 0;}
           
          
         
        
       

 

 

Sum

只看题面

•  26.14%
•  1000ms
• 512000K

 

A square-free integer is an integer which is indivisible by any square number except 11. For example, 6 = 2 \cdot 36=2⋅3 is square-free, but 12 = 2^2 \cdot 312=22⋅3 is not, because 2^222 is a square number. Some integers could be decomposed into product of two square-free integers, there may be more than one decomposition ways. For example, 6 = 1\cdot 6=6 \cdot 1=2\cdot 3=3\cdot 2, n=ab6=1⋅6=6⋅1=2⋅3=3⋅2,n=aband n=ban=ba are considered different if a \not = ba̸=b. f(n)f(n) is the number of decomposition ways that n=abn=ab such that aa and bb are square-free integers. The problem is calculating \sum_{i = 1}^nf(i)∑i=1n​f(i).

Input

The first line contains an integer T(T\le 20)T(T≤20), denoting the number of test cases.

For each test case, there first line has a integer n(n \le 2\cdot 10^7)n(n≤2⋅107).

Output

For each test case, print the answer \sum_{i = 1}^n f(i)∑i=1n​f(i).

Hint

\sum_{i = 1}^8 f(i)=f(1)+ \cdots +f(8)∑i=18​f(i)=f(1)+⋯+f(8)

=1+2+2+1+2+4+2+0=14=1+2+2+1+2+4+2+0=14.

样例输入复制

258

样例输出复制

814

题目来源

这个可以整除分块，首先搞除整除分块最常用的公式

for(int l=1,r;l<=n;l=r+1){    r=n/(n/l);    ans+=(r-l+1)*(n/l);}

但是这个题目中，你需要考虑其他情况

这个做法是sqrt(n)的

#include
           
            #include
            
             using namespace std;#define lson l,(l+r)/2,rt<<1#define rson (l+r)/2+1,r,rt<<1|1#define dbg(x) cout<<#x<<" = "<< (x)<< endl#define pb push_back#define fi first#define se second#define ll long long#define sz(x) (int)(x).size()#define pll pair
             
              #define pii pair
              
               #define pq priority_queueconst int N=2e7+5,MD=1e9+7,INF=0x3f3f3f3f;const ll LL_INF=0x3f3f3f3f3f3f3f3f;const double eps=1e-9,e=exp(1),PI=acos(-1.);int a[N];int main(){    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);    for(int i=2; i*i
               
                >T;    while(T--)    {        int n;        cin>>n;        ll ans=0;        int l=1,r;        while(l<=n)        {            r=n/(n/l)+1;            ans+=1LL*(r-l)*(n/l)-2LL*(a[r-1]-a[l-1])*(n/l)+1LL*(a[r-1]-a[l-1])*a[n/l];            l=r;        }        cout<
                
                 <<"\n"; } return 0;}
                
               
              
             
            
           

 

 

Fear Factoring The Slivians are afraid of factoring; it’s just, well, difficult. Really, they don’t even care about the factors themselves, just how much they sum to. We can define F(n) as the sum of all of the factors of n; so F(6) = 12 and F(12) = 28. Your task is, given two integers a and b with a ≤ b, to calculate S = X a≤n≤b F(n). Input The input consists of a single line containing space-separated integers a and b (1 ≤ a ≤ b ≤ 1012; b − a ≤ 106 ). Output Print S on a single line. Sample Input and Output 101 101 102 28 28 56 1 10 87 987654456799 987654456799 987654456800 2017 Pacific Northwest Region Programming Contest 9 963761198400 963761198400 5531765944320 5260013877 5260489265 4113430571304040

秦皇岛前的最后一场训练，攒人品

枚举约数

显然对于一个约数 dd ， 在 1−n1−n 中出现过 ⌊nd⌋⌊nd⌋ 次， 所以这一约数贡献的答案为 ⌊nd⌋∗d⌊nd⌋∗d

所以 1−n1−n 总因数和为

∑i=1n⌊ni⌋∗i

所以可以直接数论分块啊

#include
           
            using namespace std;typedef unsigned long long ll;ll la(ll n){    if(n==0)return 0;    ll ans=0,l=1,r=0;    for(;l<=n;)    {        r=n/(n/l);        ans+=(l+r)*(r-l+1)/2*(n/l);        l=r+1;    }    return ans;}int main(){    ll a,b;    while(~scanf("%llu%llu",&a,&b))    printf("%llu\n", la(b)-la(a-1));    return 0;}