spoj ABA12D 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 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105

this method is not good..........but u learn a lot form this logic..... if u have any doubt u can comment me........in this logic MY AC solutiin is #include<bits/stdc++.h> using namespace std; typedef long long int ll; ll ans[1000002]; inline ll sumofdiv(ll a) { ll sum=0,step=1; if(a&1) step=2; for(ll i=1;i*i<=a;i+=step) sum+=(a%i)?0:(((i*i)==a)?i:(i+a/i)); return sum; } inline ll mulmod(ll a,ll b,ll mod) { ll x=0,y=a%mod; while(b) { if(b&1) x=(x+y)%mod; y=(y<<=1)%mod; b>>=1; } return x; } inline ll pow(ll a,ll b,ll mod) { ll ans=1; a%=mod; while(b) { if(b&1) ans=mulmod(ans,a,mod); a=mulmod(a,a,mod); b>>=1; } return ans; } inline bool rabinMiller(ll n,int it) { if(n<2) return false; if(n==2) return true; if((n&1)==0) return false; ll s=n-1; while(s%2==0) s>>=1; while(it--) { ll a=rand()%(n-1)+1; ll temp=s; ll mod=pow(a,temp,n); if(mod==-1 || mod==1) continue; while(mod!=(n-1) && temp!=(n-1)) { mod=mulmod(mod,mod,n); temp<<=1; } if(mod!=(n-1)) return false; } return true; } int main() { ll t,a,b; ans[0]=0; ans[1]=0; ans[2]=1; for(ll i=3;i<1000001;i++) { if(sqrt(i)==(ll)sqrt(i)) { if(rabinMiller(sumofdiv(i),2)) { ans[i]=ans[i-1]+1; //printf("i=%lld\n",i); } else ans[i]=ans[i-1]; } else ans[i]=ans[i-1]; } scanf("%lld",&t); while(t--) { scanf("%lld %lld",&a,&b); printf("%lld\n",ans[b]-ans[a-1]); } return 0; }