PROBLEM LINK:
Setter: Abhishek Pandey
Tester: Taranpreet Singh
Editorialist: This person
DIFFICULTY:
Simple (if you can understand the evil function of Setter :D)
PREREQUISITES:
Precomputation, Sieve of Eratosthenes and Prefix Sums would be enough.
PROBLEM:
Given T ranges L_i and R_i, compute the evil function for each range. Evil function can be referred from problem statement.
SUPER QUICK EXPLANATION
-
For $x$, The flag given in problem is 0, if and only if $x$ is prime. -
Suppose we have an array $A$, $A[x] = x^x$, if $x$ is prime, else 0. - We just need Sum of A[x] for x \in [L_i, R_i], This can be easily done with Prefix Sum or Segment tree, as you wish to.
EXPLANATION
Let us discuss the evil function of Setter first.
- Notice the innermost loop on variable j. It is just checking whether j is prime, by common prime testing in O(sqrt(N)). cantCheckJ is 0 if and only if j is prime.
- If j is prime, it checks whether i is divisible by j, setting flag = 1 if i%j == 0.
- So, Indirectly this function is checking for every i if i is divisible by any prime number from 2 to i-1, that is, checking if i is prime or not.
- If i is prime, it adds i^i to answer.
So, we can simply write above function as
For x \in [L_i, R_i], if(isPrime(x))Sum+=x^x
Sub-task one can be solved by this much, but Don’t you expect 100 points, just by translating Vijju’s evil function, since Taran was devil enough to ask so many queries. (To time out their solutions in I/O itself)
For subtask two, we need to do something more.
Let us denote ans(L, R) as the answer for query(L,R).
We can notice that ans(L,R) can be represented as ans(1, R)- ans(1, L-1). You can verify that by observation as well as Mathematical Induction.
So, it suffices just to find ans(1, x) for all x \in [1, 10^5]. Also, ans(1, P) can also be written as ans(1, P-1) + A[P].
So, what are you waiting for?? Just compute prefix sum of array A and print ans[R]-ans[L-1] as answer.
Getting WA??, That’s probably because of modulo. It is possible that ans[L-1] is greater than ans[R] since we are working in modulo. So,we get the answer in negative. IN order to overcome this, I am giving you all a lifetime modulo hack. 
Answer if (ans[R]-ans[L]+mod)%mod. The proof is left as an exercise.
Complexity:
Precomputation take O(MAX) time and per query time is O(1). MAX = 10^5 for this problem.
So, overall complexity is O(MAX+T).
AUTHOR’S AND TESTER’S SOLUTIONS:
Click to view
/*
*
********************************************************************************************
* AUTHOR : Vijju123 *
* Language: C++14 *
* Purpose: - *
* IDE used: Codechef IDE. *
********************************************************************************************
*
Comments will be included in practice problems if it helps ^^
*/
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
vector<int> primes;
bool isComposite[100001]={1,1};
long long ans[100001]={0};
void sieve()
{
int i,j;
for(i=2;i<=100000;i++)
{
if(!isComposite[i])
primes.push_back(i);
//cout<<"i="<<i<<" Marked composite: ";
for(j=0;j<primes.size() and i*primes[j]<=100000;j++)
{
isComposite[i*primes[j]]=1;
//cout<<i*primes[j]<<" ";
if(i%primes[j]==0)break;
}
//cout<<endl;
}
}
int mod=pow(10,9)+7;
int fastExpo(int a,int n)
{
if(n==1)return a;
else if(n==2)return 1LL*a*a%mod;
else if(n&1)return 1LL*a*fastExpo(fastExpo(a,n>>1),2)%mod;
else return fastExpo(fastExpo(a,n>>1),2);
}
int main() {
// your code goes here
//#ifdef JUDGE
//freopen("Large10.txt", "rt", stdin);
//freopen("O-Large10.txt", "wt", stdout);
//#endif
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int t,i;
sieve();
for(i=2;i<=100000;i++)
{
if(!isComposite[i])
{
ans[i]+=fastExpo(i,i);
ans[i]%=mod;
}
ans[i]+=ans[i-1];
ans[i]%=mod;
}
//for(i=1;i<=10;i++)cout<<ans[i]<<" ";cout<<endl;
//for(int i=1;i<=10;i++)cout<<primes[i]<<" ";cout<<endl;
cin>>t;
//assert(t==100000);
int l,r,a,b;
while(t--)
{
cin>>a>>b;
assert(a<=b and a>0 and b>0);
l=lower_bound(primes.begin(),primes.end(),a)-primes.begin();
r=upper_bound(primes.begin(),primes.end(),b)-primes.begin()-1;
if(r<0)
{
assert((mod+ans[b]-ans[a-1])%mod==0);
cout<<0<<'\n';
continue;
}
//cout<<l<<" "<<r<<endl;
l=primes[l];
r=primes[r];
//cout<<a<<" "<<b<<" "<<l<<" "<<r<<endl;
assert((mod+ans[b]-ans[a-1])%mod==(mod+ans[r]-ans[l-1])%mod);
cout<<(mod+ans[r]-ans[l-1])%mod<<"\n";
}
return 0;
}
Click to view
import java.util.*;
import java.io.*;
import java.text.*;
//Solution Credits: Taranpreet Singh
public class Main{
//SOLUTION BEGIN
void solve(int TC) throws Exception{
long[] sum = new long[MAX];
boolean[] comp = new boolean[MAX];
for(int i = 2; i< MAX; i++)if(!comp[i]){
sum[i] = pow(i,i);
for(int j = i+i; j< MAX; j+=i)comp[j] = true;
}
for(int i = 1; i< MAX; i++)sum[i] = (sum[i]+sum[i-1])%mod;
for(int qq = ni(); qq>0;qq--)pn((mod-sum[ni()-1]+sum[ni()])%mod);
}
int time = 0;
long pow(long a, long p){
long o = 1;
while(p>0){
if(p%2==1)o = (o*a)%mod;
p/=2;
a = (a*a)%mod;
}
return o;
}
//SOLUTION ENDS
long mod = (int)1e9+7, IINF = (long)1e12;
final int MAX = (int)1e5+1, INF = (int)1e9, root = 3;
DecimalFormat df = new DecimalFormat("0.00000000");
double PI = 3.141592653589793238462643383279502884197169399375105820974944, eps = 1e-8;
static boolean multipleTC = false, memory = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
for(int i = 1, T= (multipleTC)?ni():1; i<= T; i++)solve(i);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
else new Main().run();
}
long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n(){return in.next();}
String nln(){return in.nextLine();}
int ni(){return Integer.parseInt(in.next());}
long nl(){return Long.parseLong(in.next());}
double nd(){return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next(){
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
e.printStackTrace();
}
}
return st.nextToken();
}
String nextLine(){
String str = "";
try{
str = br.readLine();
}catch (IOException e){
e.printStackTrace();
}
return str;
}
}
}
)