SHLQSH数

末蓝、 2021-11-02 14:32 148阅读 0赞

刚开始时用了算约数个数公式，果断超时。。

#include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <stdlib.h>
    
    char prime[5000010]={
         0};
    int dp[700000];
    const int inf = 3500;
    int k, a, b, l;
    struct node {
         
    int v;
    int n;
    }val[1000];
    
    void fun( )
    {
         
    int i, j;
    for ( i = 3; i <= inf; i += 2)
    if ( prime[i / 2] == 0) {
         
    for (j = i * i; j <= 10000000; j += i + i)
                 prime[j / 2] = 1;
             } 
         dp[0] = 2;
         k = 1;
    for ( i = 1; i < (10000000 + 1) / 2;  i++)
    if( prime[i] != 1)
                 dp[k++] = i * 2 + 1;
    }
    
    void solve(int a)
    {
         
    int i, j, flag = 0;
         l = 0;
    for(i = 0; i < k; i++) {
         
    while(a % dp[i] == 0) {
         
                       val[l].v = dp[i];
                       val[l].n++;
                       a = a / dp[i];
                       flag = 1;
    if(a == 0)
    break;
                    }
    if(flag)
                            l++;
                    flag = 0;
    if(a == 0)
    break;
        }
    }
    
    void init( )
    {
         
    int i;
    for ( i = 0; i < l; i++)
             val[i].n = 0;
    }
    
    
    int main( )
    {
         
    int i, j, sum, s;
        fun( );
    while (scanf("%d%d", &a, &b), a || b)
        { 
          sum = 0;
    for (i = a; i <= b; i++) {
         
             solve(i);
             s = 1;
    for ( j = 0; j < l; j++)
                 s *= (1+ val[j].n);
                 sum += s;
             init( );
          }
         printf("%d\n",sum);
    
        }
    return 0;
    }

后来才知道这题有非常巧妙的算法。。、

#include<stdio.h>
    #include<stdlib.h>
    int t1, t2, a, i;
    int main()
    {
         
    while(scanf("%d%d",&t1,&t2),t1 || t2) {
         
        a = 0;                       
        t1--;
    for (i = 1;i <= t1; i++)
             a -= t1 / i;
    for (i = 1;i <= t2; i++)
             a += t2 / i;
        printf("%d\n", a);
        }    
    return 0;
    }

转载于:https://www.cnblogs.com/tangcong/archive/2011/07/27/2118946.html