HDU 6069 Counting Divisors 素数，思维

　　题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=6069

　　题目描述：给出l , r , k ,求出， (∑i=d(i^k))mod998244353 （i 属于 [l, r]）, d(x) 表示x 因子的个数。l , r <= 1e12 , r-l <= 1e6

　　解题思路：比赛的时候想到唯一分解定理然后暴力的挨个遍历，这样还是会T，应该先筛出1 ~ 1e6所有的素数，再根据素数倍数来筛l ~ r之间的数。然后遇到一个特别坑的bug, 不管怎么交，都是RE（除零），可是到底哪里除零了呢，半天没找到，管北交学长要到的测试数据测一下也是正确的，后来才发现，我的prime数组是int , 这样判断 prime * prime <= r 的时候会爆掉，而OJ上爆掉就会使prime归零，而我的编译器则不会，所以说我的测试结果才是对的，然后OJ上才会出现RE（除零的错误）。

　　代码：

/*
 ID: wl199701
 PROG: namenum
 LANG: C++
 */
//#include <iostream>
//#include <cstring>
//#include <cstdio>
//#include <string>
//#include <fstream>
//#include <iterator>
//#include <map>
//#include <algorithm>
//using namespace std;
//
//const int maxn = 10000;
//string table[maxn];
//
//int main(){
////    freopen("namenum.in","r",stdin);
////    freopen("namenum.out","w",stdout);
//    
//    return 0;
//}


#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <cstring>
#include <iterator>
#include <cmath>
#include <algorithm>
#include <stack>
#include <deque>
#include <map>

using namespace std;
typedef long long ll;
const int maxn = 1e6 + 7;
int vis[maxn];
int prime[maxn];
ll cnt[maxn];
ll q[maxn];
int tot;
ll l, r, k;
const int MOD = 998244353;
int t;
ll ans;

void init() {
    memset(vis, 0, sizeof(vis));
    tot = 0;
    for( int i = 2; i <= maxn; i++ ) {
        if( !vis[i] ) {
            prime[tot++] = i;
        }
        for( int j = i*2; j <= maxn; j += i ) {
            vis[j] = 1;
        }
    }
    
}

int main() {
//    freopen("in.txt", "r", stdin);
    int t;
    init();
//    for( int i = 0; i < tot; i++ ) {
//        if( !prime[i] ) cout << "=========" << endl;
//    }
    scanf( "%d", &t );
    while( t-- ) {
        scanf( "%lld%lld%lld", &l, &r, &k );
        memset(q, 0, sizeof(q));
        memset(cnt, 0, sizeof(cnt));
        ll ans = 0;
        if( l == 1 ) ans++, l++;
        for( ll i = 0; i <= r-l; i++ ) {
            cnt[i] = 1;
            q[i] = l+i;
        }
        for( ll i = 0; (ll)prime[i]*(ll)prime[i] <= r; i++ ) {
            ll j = l / prime[i] + (l % prime[i] != 0);

            for( j = j * prime[i]; j <= r; j += prime[i] ) {
                ll temp = 0;
                while( q[j-l] % prime[i] == 0 ) {
                    q[j-l] /= prime[i];
                    temp++;
                }
                cnt[j-l] *= (k * temp) % MOD + 1;
                cnt[j-l] %= MOD;
            }
        }
        for( ll i = 0; i <= r-l; i++ ) {
            if( q[i] != 1 ) ans += (cnt[i]  *(k+1)) % MOD;
                
            else ans += cnt[i];
            ans %= MOD;

        }
        printf( "%lld
", ans % MOD );
        
    }
    return 0;
}

View Code

　　思考：这道题我没有想出来，明明感觉自己以前做过......然后就是以后尽量统一类型，浪费不了多少空间，不同编译器处理不同异常的方式不一样，注意溢出问题

HDU 6069 Counting Divisors 素数， 思维

HDU 6069 Counting Divisors 素数，思维