#include<bits/stdc++.h>
using namespace std;
const int N=100002;
int T,i,is[N],j,cnt,sum,a,b,c,d,k,t,ca;
long long ans;
vector<int>x[N];
int main(){
for (i=2;i<N;i++)
if (!is[i])
for (j=i;j<N;j+=i) is[j]=1,x[j].push_back(i);
scanf("%d",&T);
while (T--){
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
if (!k){
printf("Case %d: 0\n",++ca);
continue;
}
b/=k;d/=k;ans=0;
if (b>d) swap(b,d);
for (i=1;i<=d;i++){
k=min(i,b);ans+=k;
for (j=1;j<1<<x[i].size();j++){
cnt=0;sum=1;
for (t=0;t<x[i].size();t++)
if (j&(1<<t)) cnt^=1,sum*=x[i][t];
if (cnt) cnt=-1;
else cnt=1;
ans+=k/sum*cnt;
}
}
printf("Case %d: %lld\n",++ca,ans);
}
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int i,j,k,pri[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61};
ll tmp,ans,n;
int main(){
while (~scanf("%lld",&n)){
ans=1;
for (i=0;;i++){
tmp=pow(n,1.0/pri[i]);
if (tmp<2) break;
ans+=tmp-1;
for (j=i+1;;j++){
tmp=pow(n,1.0/pri[i]/pri[j]);
if (tmp<2) break;
ans-=tmp-1;
for (k=j+1;;k++){
tmp=pow(n,1.0/pri[i]/pri[j]/pri[k]);
if (tmp<2) break;
ans+=tmp-1;
}
}
}
printf("%lld\n",ans);
}
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=400002;
int n,m,i,x,y,op,z,b[N],T,pri[N/10],f[20],num,cnt,tot,pos[1002],j,a[N],t;
ll ans;
void div(int x){
num=0;
for (int i=0;pri[i]*pri[i]<=x && i<tot;i++)
if (x%pri[i]==0){
f[num++]=pri[i];
while (x%pri[i]==0) x/=pri[i];
}
if (x>1) f[num++]=x;
}
ll calc(int x){
ll sum=0;
for (int i=1;i<1<<num;i++){
int cnt=0;ll s=1;
for (int j=0;j<num;j++)
if (i&(1<<j)) cnt^=1,s*=f[j];
if (!cnt) cnt--;
ll k=x/s;
sum+=k*(k+1)/2*s*cnt;
}
return (ll)x*(x+1)/2-sum;
}
int main(){
scanf("%d",&T);
for (i=2;i<N;i++){
if (!b[i]) pri[tot++]=i;
for (j=0;j<tot && (ll)i*pri[j]<N;j++){
b[i*pri[j]]=1;
if (i%pri[j]==0) break;
}
}
while (T--){
scanf("%d%d",&n,&m);
memset(a,0,sizeof(a));
cnt=0;
while (m--){
scanf("%d%d%d",&op,&x,&y);
if (op==1){
scanf("%d",&z);
div(z);
ans=calc(y)-calc(x-1);
for (i=0;i<cnt;i++){
t=pos[i];
if (x<=t && t<=y){
if (__gcd(t,z)==1) ans-=t;
if (__gcd(a[t],z)==1) ans+=a[t];
}
}
printf("%lld\n",ans);
}else{
if (!a[x]) pos[cnt++]=x;
a[x]=y;
}
}
}
}
#include<bits/stdc++.h>
using namespace std;
const int M=1000007;
int T,i,r,c,n,m,s,cnt,ans,k,C[500][500],ca,j;
int main(){
scanf("%d",&T);
for (i=0;i<500;i++){
C[i][0]=1;
for (j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%M;
}
while (T--){
scanf("%d%d%d",&n,&m,&k);
ans=0;
for (s=0;s<16;s++){
r=n;c=m;cnt=0;
if (s&1) cnt^=1,r--;
if (s&2) cnt^=1,r--;
if (s&4) cnt^=1,c--;
if (s&8) cnt^=1,c--;
cnt=cnt?-1:1;
(ans+=C[r*c][k]*cnt)%=M;
}
printf("Case %d: %d\n",++ca,(ans+M)%M);
}
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100002;
ll ans;
int T,i,j,n,m,cnt,b[N],pri[N/10],mu[N];
int main(){
scanf("%d",&T);
mu[1]=1;
for (i=2;i<N;i++){
if (!b[i]) pri[cnt++]=i,mu[i]=-1;
for (j=0;j<cnt && i*pri[j]<N;j++){
b[i*pri[j]]=1;
if (!(i%pri[j])){
mu[i*pri[j]]=0;
break;
}
mu[i*pri[j]]=-mu[i];
}
mu[i]+=mu[i-1];
}
while (T--){
scanf("%d%d",&n,&m);
ans=0;
for (i=1;i<=min(n,m);i=j+1){
j=min(n/(n/i),m/(m/i));
ans+=(ll)(mu[j]-mu[i-1])*(n/i)*(m/i);
}
printf("%lld\n",ans);
}
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,ca,f[20],num,n;
ll q[100003],a,b;
void div(int x){
for (int i=2;i*i<=x;i++)
if (x%i==0){
f[num++]=i;
while (x%i==0) x/=i;
}
if (x>1) f[num++]=x;
}
ll cal(ll x){
int t=1;ll sum=0;
q[0]=-1;
for (int i=0;i<num;i++){
int k=t;
for (int j=0;j<k;j++) q[t++]=-1*q[j]*f[i];
}
for (int i=1;i<t;i++) sum+=x/q[i];
return sum;
}
int main(){
scanf("%d",&T);
while (T--){
num=0;
scanf("%lld%lld%d",&a,&b,&n);
div(n);
printf("Case #%d: %lld\n",++ca,b-cal(b)-(a-1-cal(a-1)));
}
}
#include<cstdio>
using namespace std;
typedef long long ll;
ll ans,l,r,mid;
int n,k,i,x,t,num,f[20],q[100002],j,m;
ll check(ll x){
ll sum=0;
for (int i=1;i<t;i++) sum+=x/q[i];
return x-sum;
}
int main(){
while (~scanf("%d%d",&n,&m)){
x=n;num=0;
for (i=2;i*i<=x;i++)
if (x%i==0){
f[num++]=i;
while (x%i==0) x/=i;
}
if (x>1) f[num++]=x;
t=1;
q[0]=-1;
for (i=0;i<num;i++){
k=t;
for (j=0;j<k;j++) q[t++]=-q[j]*f[i];
}
l=0;r=1e18;
while (l<=r){
mid=l+r>>1;
if (check(mid)<m) l=mid+1;
else r=mid-1,ans=mid;
}
printf("%lld\n",ans);
}
}
#include<bits/stdc++.h>
using namespace std;
const int M=1e9+7;
typedef long long ll;
int n,k,i,j,w;
ll ans,f[1002],c[1002][1002];
class CarelessSecretary{
public:
int howMany(int n,int k){
memset(c,0,sizeof(c));
for (i=0;i<=n;i++){
c[i][0]=1;
for (j=1;j<=i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%M;
}
f[1]=0;f[2]=1;
for (i=3;i<=n;i++) f[i]=(f[i-1]+f[i-2])*(i-1)%M;
ans=0;w=n-k;
for (i=0;i<=w;i++) (ans+=c[w][i]*f[n-i])%=M;
return (int)ans;
}
};
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=502,P=999983;
string good;
int n;
int m,i,j,k;
ll tmp,f[52][M],k1,k2;
class CharmingTicketsEasy{
public:
int count(int n,string good){
scanf("%d",&n);cin>>good;
m=good.size();
memset(f,0,sizeof(f));
f[0][0]=1;
tmp=k1=k2=0;
for (i=1;i<=n;i++)
for (k=0;k<m;k++)
for (j=good[k]-'0';j<M;j++) (f[i][j]+=f[i-1][j-good[k]+'0'])%=P;
for (i=0;i<M;i++) (tmp+=f[n][i]*f[n][i])%=P,(k1+=f[n/2][i]*f[n/2][i])%=P;
if (n&1)
for (i=0;i<M;i++) (k2+=f[n-n/2][i]*f[n-n/2][i])%=P;
else k2=k1;
return (tmp*2-k1*k2%P+P)%P;
}
};
#include<bits/stdc++.h>
using namespace std;
const int M=1000003;
int i,j,st,cnt,f[52][1<<15],len,ans,n;
char c;
class SetOfPatterns{
public:
int howMany(vector<string>s,int k){
n=s.size();
len=s[0].size();
for (i=0;i<len;i++)
for (c='a';c<='z';c++){
st=0;
for (j=0;j<n;j++)
if (s[j][i]=='?' || s[j][i]==c) st|=1<<j;
if (!i) f[i][st]++;
else for (j=0;j<1<<n;j++) (f[i][st&j]+=f[i-1][j])%=M;
}
for (i=0;i<1<<n;i++){
cnt=0;
for (j=0;j<n;j++)
if (i&(1<<j)) cnt++;
if (cnt==k) (ans+=f[len-1][i])%=M;
}
return ans;
}
};
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
typedef unsigned long long ll;
int i,j,w,x,x1,x2,n;
ll f[15][1<<15],p[16],sum;
class Deranged{
public:
ll numDerangements(vector<int>a){
n=a.size();
f[0][0]=1;x1=0;x2=1;
for (w=0;w<n;w++,x1^=1,x2^=1){
memset(f[x2],0,sizeof(f[x2]));
for (i=0;i<1<<n;i++)
for (j=0;j<n;j++)
if (!(i&(1<<j)) && a[w]!=a[j]) f[x2][i|(1<<j)]+=f[x1][i];
}
sum=f[x1][(1<<n)-1];
p[0]=1;
for (i=1;i<=n;i++) p[i]=p[i-1]*i;
for (i=0;i<n;i++){
x=0;
for (j=0;j<n;j++) x+=a[j]==i;
sum/=p[x];
}
return sum;
}
};
#include<bits/stdc++.h>
const int N=202;
using namespace std;
typedef long long ll;
ll c[N][N],ans;
int i,j;
class TheHexagonsDivOne{
public:
ll count(int n){
for (i=0;i<N;i++){
c[i][0]=1;
for (j=1;j<=i;j++) c[i][j]=c[i-1][j]+c[i-1][j-1];
}
ans=2*n;
ans=ans*(7680*c[n-1][6]+5760*c[n-1][5]+1152*c[n-1][4]+32*c[n-1][3]);
return ans;
}
};
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10002;
int n,i,j,b[N],cnt[N],sef[N],num[N],mx,x;
ll ans;
ll cal(int x){
return (ll)x*(x-1)*(x-2)*(x-3)/24;
}
int main(){
for (i=1;i<N;i++) sef[i]=1,cnt[i]=-1;
for (i=2;i<N;i++)
if (!b[i])
for (j=i;j<N;j+=i){
sef[j]*=i;
cnt[j]*=-1;
b[j]=1;
}
while (~scanf("%d",&n)){
memset(num,0,sizeof(num));
ans=mx=0;
for (i=0;i<n;i++) scanf("%d",&x),num[x]++,mx=max(mx,x);
if (n<4){
puts("0");
continue;
}
for (i=2;i<=mx;i++)
for (j=i+i;j<=mx;j+=i) num[i]+=num[j];
for (i=2;i<=mx;i++)
if (sef[i]==i) ans+=cal(num[i])*cnt[i];
printf("%lld\n",cal(n)-ans);
}
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10000002;
int T,i,cnt[N],sef[N],m,b[N],j;
ll n,ans;
int main(){
scanf("%d",&T);
for (i=1;i<N;i++) cnt[i]=-1,sef[i]=1;
for (i=2;i<N;i++)
if (!b[i])
for (j=i;j<N;j+=i){
sef[j]*=i;
cnt[j]*=-1;
b[j]=1;
}
while (T--){
scanf("%lld",&n);
m=sqrt(n);ans=0;
for (i=2;i<=m;i++)
if (sef[i]==i) ans+=cnt[i]*n/((ll)i*i);
printf("%lld\n",n-ans);
}
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1e8+7;
int T;ll n,inv;
ll pw(ll x,ll y){
ll z=1;
for (;y;y>>=1,x=x*x%M)
if (y&1) z=z*x%M;
return z;
}
int main(){
scanf("%d",&T);
inv=pw(2,M-2);
while (T--){
scanf("%lld",&n);
printf("%lld %lld\n",(pw(3,n)-pw(2,n+1)+1+M)%M*inv%M,
(pw(4,n)-pw(3,n+1)+pw(2,n)*3%M-1+M*2)%M*inv%M);
}
}
京公网安备 11010502036488号