acm-icpc regionals amritapuri 2014

Kiwi Number

The New Zealand government is super-excited about the Cricket World Cup 2015 happening in their country. Hence, it has decided to conduct a census on cricket to find out how many people are interested in the sport, etc.
The statistics obtained are given to us as a range of numbers from A to B (inclusive). In these statistics, the government is interested in some particular numbers called "Kiwi Numbers".
A number is called a Kiwi Number if it has a prime number of distinct factors. A prime number N has exactly two divisors, 1 and N.
Can you help the government by calculating the number of Kiwi numbers in the given range?
Input:
The first line contains the number of test cases T.
Each of the next T lines contains two space separated numbers A and B.
Output:
For each test case, output the required answer on a separate line.
Constaints:
1 <= T <= 100
2 <= A <= B <= 1000000000
B - A <= 200000
Sample Input:
3
2 10
100 100
578 720
Sample Output:
6
0
23
Explanation:
For the first case, the Kiwi numbers are 2, 3, 4, 5, 7, 9.

explainantion

 to solve this u need to know segmented sieve of Eratosthenes ....
solve  this spoj question for detail...

http://www.spoj.com/problems/PRIME1/


solution

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

#include<bits/stdc++.h> int a[10000]={0}; int main() { a[1]=1; a[0]=1; for(int i=6;i<=100;i+=6) { if(a[i-1]==0) for(int j=(i-1)*(i-1);j<=10000;j+=(i-1)) a[j]=1; if(a[i+1]==0) for(int j=(i+1)*(i+1);j<=10000;j+=(i+1)) a[j]=1; } int t,n,m; scanf("%d",&t); while(t--) { int b[200005]={0},z=0; scanf("%d %d",&n,&m); int x=sqrt(m); for(int i=2;i<=x;i++) { int k=n/i; k=k*i; if(k<n)k+=i; int sq=i*i; for(;k<=m;k+=i) { if(k<sq)continue; if(k==sq)b[k-n]++; else b[k-n]+=2; } } for(int i=0;i<=m-n;i++) { b[i]+=2; if(b[i]==2 || b[i]==3)z++; if(a[b[i]]==0 && b[i]%2!=0 && b[i]%3!=0) z++; } printf("%d\n",z); } return 0; }

Dhonis Bowlers

The Indian team is known for their strong batting and sloppy bowling. The captain M.S. Dhoni is concerned about this issue. He wants to address this by pairing up bowlers who have good economy rates.

He has all the bowlers' economy rates as integers. Unfortunately, these are T20 figures and to convert them to ODI format, he wants to pair up bowlers in such a way that the sum of the economy rates of two bowlers, modulo M, is always less than or equal to X.

Given the economy rates, M and X, can you tell him how many such ordered pairs are possible?

Note: The pair of bowlers chosen by him can be the same. Yeah, Dhoni has won a cup in all limited over formats, but he definitely needs to sharpen his math skills.

Input:

The first line contains the number of test cases T. Each test case contains N, M and X on the first line, followed by N space separated integers A[1..N] on the second line.

Output:

Output T lines, containing the answer for the corresponding test case.

Constraints:

1 <= T <= 10

1 <= N <= 100000

0 <= X < M <= 100000

0 <= A[i] <= 1000000000

Sample Input:

2

3 5 3

1 2 3

4 7 4

31 12 11 17

Sample Output:

6

12

Explanation:

For the first example, the valid pairs are (1, 1), (1, 2), (2, 1), (2, 3), (3, 2), (3, 3).

my solution

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

#include<bits/stdc++.h> using namespace std; int main() { int t; scanf("%d",&t); while(t--) { int n,m,x,a[300000]={0},c,window[300000]={0}; long long sum=0; scanf("%d %d %d",&n,&m,&x); for(int i=0;i<n;i++) { scanf("%d",&c); a[c%m]++; } window[0]=a[0]; for(int i=1;i<m;i++) window[i]=window[i-1]+a[i]; for(int i=m;i<=m+x;i++) window[i]=window[i-1]; for(int i=0;i<m;i++) { if(x>=i) sum+=a[i]*(window[x-i]); sum+=a[i]*(window[m+x-i]-window[m-i-1]); } printf("%lld\n",sum ); } return 0; }