1003. Counting Divisors


先去打一个1到1e6的素数表，然后去枚举每个素数在区间内的倍数，可以跳着枚举，计算出每个数对应的因子个数，对于每个数的因子个数就等于枚举的因子个数*k+1累乘起来。累加该区间内所有数的统计结果即为最终答案。
于是我们考虑枚举 r√ 以内的所有质数 i ，并在区间 [l,r] 中对 i 的倍数计算其含有多少 i 这个质因子，统计结果。
随后考虑每个数在 r√ 以外的质因子，若有，则统计这部分。
现场做的时候没想到，家旺想到了枚举根号r，简化运算，被我给否决了。。。。但是还是没有想到用根号r内的质数去再分解质因数。。。 
#include <iostream>  
#include <cstdio>  
#include <cstring>  
using namespace std;  
typedef long long ll;  
const int maxn = 1000000+10;  
const ll mod = 998244353;  
ll g[maxn];///g[i]表示数i+l有多少个因子  
ll f[maxn];///f[i]表示第i个数是i+l,f[i]数组用来分解质因数  
ll p[maxn];  
bool vis[maxn];  
int main()  
{  
    ///处理根r以内的素数  
    int total = 0;  
    for(int i = 2;i<maxn;++i){  
        if(!vis[i]){///非偶  
            p[++total] = i;  
        }  
        for(int j = 1;j<=total && p[j]*i<maxn;++j){  
            vis[i*p[j]] = 1;  
            if(i%p[j]==0) break;  
        }  
    }  
  
    int t;  
    scanf("%d",&t);  
    while(t--){  
        ll l,r,k;  
        scanf("%lld%lld%lld",&l,&r,&k);  
        for(ll i = 0;i<r-l+1;++i){///映射，把l~r映射到从下标0~r-l  
            f[i] = i+l;  
            g[i] = 1;  
        }  
        for(ll i = 1;i<=total && p[i]*p[i]<=r;++i){///枚举根r以内的素数就够了  
            for(ll j = l/p[i]*p[i];j<=r;j+=p[i]){///枚举属于l~r之间的p[i]的倍数  
                if(j<l) continue;///l/p[i]*p[i] 可能是小于l（字母L）的数或者是l  
                int cnt = 0;  
                while(f[j-l]%p[i] == 0){  
                    f[j-l]/=p[i];  
                    cnt++;  
                }  
                g[j-l] = (g[j-l]*(cnt*k+1))%mod;  
            }  
        }  
        ll ans = 0;  
        for(int i = 0;i<r-l+1;++i){  
            if(f[i]>1){///说明这个数没有被除完，这个数是个质因子  
                g[i] = g[i]*(1*k+1) % mod;  
            }  
            ans = (ans+g[i])%mod;  
        }  
        printf("%lld\n",ans);  
    }  
    return 0;  
}


1009. Questionnaire

Questionnaire

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1585    Accepted Submission(s): 914
Special Judge

Problem Description
In order to get better results in official ACM/ICPC contests, the team leader comes up with a questionnaire. He asked everyone in the team whether to have more training.

<center>

Picture from Wikimedia Commons
</center>

Obviously many people don't want more training, so the clever leader didn't write down their words such as ''Yes'' or ''No''. Instead, he let everyone choose a positive integer  ai to represent his opinion. When finished, the leader will choose a pair of positive interges  m(m>1) and  k(0≤k<m), and regard those people whose number is exactly  k modulo  m as ''Yes'', while others as ''No''. If the number of ''Yes'' is not less than ''No'', the leader can have chance to offer more training.

Please help the team leader to find such pair of  m and  k.
 

Input
The first line of the input contains an integer  T(1≤T≤15), denoting the number of test cases.

In each test case, there is an integer  n(3≤n≤100000) in the first line, denoting the number of people in the ACM/ICPC team.

In the next line, there are  n distinct integers  a1,a2,...,an(1≤ai≤109), denoting the number that each person chosen.
 

Output
For each test case, print a single line containing two integers  m and  k, if there are multiple solutions, print any of them.
 

Sample Input
1 6 23 3 18 8 13 9
 

Sample Output
5 3

注意special judge 只需要取特殊情况，m=2，进行判断即可。

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <cmath>  
using namespace std;

int a[100005];  

int main(){
    int t;
    while(~scanf("%d",&t)){
        while(t--){
            int n;
            scanf("%d",&n);
            memset(a,0,sizeof(a));
            for(int i=0;i<n;i++){
                scanf("%d",&a[i]);
            }
            int cnt1=0;
            int cnt2=0;
            for(int i=0;i<n;i++){
                if(a[i]%2==1){
                    cnt1++;
                }
                else cnt2++;
            }
            if(cnt1>=cnt2){
                printf("2 1\n");
                continue;    
            }
            else{
                printf("2 0\n");
                continue;
            }
        }    
    }
    
    return 0;
}


1011. Time To Get Up

Time To Get Up

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1362    Accepted Submission(s): 868

Problem Description
Little Q's clock is alarming! It's time to get up now! However, after reading the time on the clock, Little Q lies down and starts sleeping again. Well, he has  5 alarms, and it's just the first one, he can continue sleeping for a while.

Little Q's clock uses a standard 7-segment LCD display for all digits, plus two small segments for the '':'', and shows all times in a 24-hour format. The '':'' segments are on at all times.

<center> </center>

Your job is to help Little Q read the time shown on his clock.
 

Input
The first line of the input contains an integer  T(1≤T≤1440), denoting the number of test cases.

In each test case, there is an  7×21 ASCII image of the clock screen.

All digit segments are represented by two characters, and each colon segment is represented by one character. The character ''X'' indicates a segment that is on while ''.'' indicates anything else. See the sample input for details.
 

Output
For each test case, print a single line containing a string  t in the format of  HH:MM, where  t(00:00≤t≤23:59), denoting the time shown on the clock.
 

Sample Input
1 .XX...XX.....XX...XX. X..X....X......X.X..X X..X....X.X....X.X..X ......XX.....XX...XX. X..X.X....X....X.X..X X..X.X.........X.X..X .XX...XX.....XX...XX.
 

Sample Output
02:38

分成四段，每段的左上角分别为0,5,12,17。
然后特判一些点即可。 

#include <iostream>
using namespace std;
//2
//.XX..........XX...XX.
//...X.X..X...X..X.X...
//...X.X..X.X.X..X.X...
//......XX.....XX...XX.
//...X....X.X....X.X..X
//...X....X......X.X..X
//.............XX...XX.
//..................XX.
//...X.X..X...X..X.X...
//...X.X..X.X.X..X.X...
//......XX.....XX...XX.
//...X....X.X....X....X
//...X....X......X....X
//..................XX.
char c[10][30];
int solve(int x,int y){
    if(c[x][y+1]=='.'){
        if(c[x+3][y+1]=='.'){
            return 1;
        }
        return 4;
    }
    if(c[x+1][y]=='.'){
        if(c[x+4][y]!='.')
            return 2;
        if(c[x+6][y+1]!='.')
            return 3;
        return 7;
    }
    if(c[x+3][y+1]=='.')
        return 0;
    if(c[x+4][y]=='.'){
        if(c[x+1][y+3]=='.')
            return 5;
        return 9;
    }
    if(c[x+1][y+3]=='.')
        return 6;
    return 8;
}
int main(){
    int t;
    while(~scanf("%d",&t)){
        for(int i=0;i<t;i++){
            for(int i=0;i<7;i++){
                scanf("%s",c[i]);
            }
            cout<<solve(0,0)<<solve(0,5)<<":"<<solve(0,12)<<solve(0,17)<<endl;
        }
    }
    return 0;
}


官方题解