Görevimiz oldukça basit. Bulmanız gereken değer
(Resim anlaşılmıyor olabilir (1 < i < N) koşulunu sağlayan i değerleri için i4.floor(N/i) toplamı... )
Bu sayı büyük olabileceği için mod M’deki denkini yazdırınız.
Input Format
İlk satırda T test case sayısı
Sonraki T satırda N ve M değerleri
Output
Format
Toplam değerin mod M’deki denki…
Constraints
1 < M < 100000
2 tip dataset var:
1 < N < 106 ve 1 <
T < 3000
106 < N < 1010 ve 1
< T < 30
Input
3
4 100
2 23
3 50
Output
73
18
0
Explanation
1.Test case: (44.1 + 34.1 + 24.2
+ 14.4) ≡ 73 (mod 100)
2.Test case: (24.1 + 14.2) ≡ 18 (mod 23)
3.Test case: (34.1 + 24.1 + 14.3)
≡ 0 (mod 50)
___________________________________________________
Linkler
___________________________________________________
Çözüm
Bu soru da bazı matematik soruları gibi √N üzerinden gidilen bir soru.
İlk adımımızda (1 < i < √N) koşulunu sağlayan tüm i değerleri için i4.floor(N/i) değerini cevabımıza ekleyelim.
Sonraki adımımızda j=floor(N/i) üzerinden gideceğiz şöyle ki... (1 < j < √N && j=floor(N/i)) koşulunu sağlayacak şekilde tüm j değerleri için tüm i aralıklarını bulalım. Burada yapmamız gereken şey tüm j değerleri için i aralığındaki sayıların 4.kuvvetlerinin toplamının floor(N/i) yani j ile çarpımını cevabımıza eklemek.
Peki bir aralıktaki sayıların 4.kuvvetleri toplamını nasıl hesaplarız? Burada kısa bir matematik formülü kullanacağız. Aşağıda size yararlı olabilecek birkaç formül var. İsterseniz boş zamanınızda ispatını yapabilirsiniz :)
Peki bir aralıktaki sayıların 4.kuvvetleri toplamını nasıl hesaplarız? Burada kısa bir matematik formülü kullanacağız. Aşağıda size yararlı olabilecek birkaç formül var. İsterseniz boş zamanınızda ispatını yapabilirsiniz :)
Kodlama detayı 1: i=floor(N/i) koşulunu sağlayan i değeri olduğunda i4.floor(N/i) değerini 2 kere eklemiş oluyoruz. Örneğin N=27 için 54.floor(27/5) değerini hem 1.adımda i=5 için hem de 2.adımda j=5 için eklemiş oluyoruz. Bu durum tüm N değerleri için geçerli değil. Örneğin [25,29] aralığı için bu durum varken [30,35] aralığı için bu yok.
Kodlama detayı 2: [L,R] aralığındaki sayıların 4.kuvvetleri toplamını hesaplayacağız. Yukarıdaki formülde gözüktüğü üzere en son /30 ifadesi olduğu için L'nin ve R'nin mod M'deki denkini işe karıştırmamamız gerektiği anlaşılmaktadır. R=N=1010 olduğunda 3N2+3N-1 değeri Long Long sınırını aşacaktır. Bu durum işimizi zorlaştırmaktadır. Bunu aşmanın çok kolay bir yolu var. O da yeni bir mod değerinde bu sayıları hesaplamak... mod=30*M olmak üzere L ve R değerini bu "mod" değerine göre modunu alıp sonrasında bu sayıları hesapladığımızda bir problem kalmıyor. Nedeni ise "mod", M'in katı olduğu için cevabı bozmamaktadır ayrıca L'nin ve R'nin bu değere göre modu alındığında Long Long sorunu ortadan kalkıyor.
#include <algorithm>
#include <stdio.h>
using namespace std;
typedef long long LL;
LL T,n,mod;
LL getpow4(LL x)
{
x%=mod;
x=(x*x)%mod;
x=(x*x)%mod;
return x;
}
LL sumpow4(LL x)
{
x%=mod*30;
LL a=x,b=x+1,c=2*x+1,d=3*x*x+3*x-1;
bool ok[3]={0,0,0};
if(a%2==0 && !ok[0]) { a/=2; ok[0]=1; }
if(a%3==0 && !ok[1]) { a/=3; ok[1]=1; }
if(a%5==0 && !ok[2]) { a/=5; ok[2]=1; }
if(b%2==0 && !ok[0]) { b/=2; ok[0]=1; }
if(b%3==0 && !ok[1]) { b/=3; ok[1]=1; }
if(b%5==0 && !ok[2]) { b/=5; ok[2]=1; }
if(c%2==0 && !ok[0]) { c/=2; ok[0]=1; }
if(c%3==0 && !ok[1]) { c/=3; ok[1]=1; }
if(c%5==0 && !ok[2]) { c/=5; ok[2]=1; }
if(d%2==0 && !ok[0]) { d/=2; ok[0]=1; }
if(d%3==0 && !ok[1]) { d/=3; ok[1]=1; }
if(d%5==0 && !ok[2]) { d/=5; ok[2]=1; }
a%=mod;
b%=mod;
c%=mod;
d%=mod;
return (((((a*b)%mod)*c)%mod)*d)%mod;
}
int main()
{
scanf("%lld",&T);
while(T--)
{
scanf("%lld%lld",&n,&mod);
LL kok=1;
while(kok*kok<=n) kok++;
kok--;
LL ans=0;
for(LL i=1 ; i<=kok ; i++)
{
LL a=(n/i)%mod;
LL b=getpow4(i);
ans=(ans+(a*b)%mod)%mod;
}
for(LL i=1 ; i<=kok ; i++)
{
LL a=sumpow4(n/i);
LL b=sumpow4(n/(i+1));
LL add=(a-b+mod)%mod;
add=(add*(i%mod))%mod;
ans=(ans+add)%mod;
}
if(n/kok==kok)
{
LL i=kok;
LL neg=getpow4(i);
neg=(neg*(i%mod))%mod;
ans=(ans-neg+mod)%mod;
}
printf("%lld\n",ans);
}
return 0;
}
Kodlama detayı 2: [L,R] aralığındaki sayıların 4.kuvvetleri toplamını hesaplayacağız. Yukarıdaki formülde gözüktüğü üzere en son /30 ifadesi olduğu için L'nin ve R'nin mod M'deki denkini işe karıştırmamamız gerektiği anlaşılmaktadır. R=N=1010 olduğunda 3N2+3N-1 değeri Long Long sınırını aşacaktır. Bu durum işimizi zorlaştırmaktadır. Bunu aşmanın çok kolay bir yolu var. O da yeni bir mod değerinde bu sayıları hesaplamak... mod=30*M olmak üzere L ve R değerini bu "mod" değerine göre modunu alıp sonrasında bu sayıları hesapladığımızda bir problem kalmıyor. Nedeni ise "mod", M'in katı olduğu için cevabı bozmamaktadır ayrıca L'nin ve R'nin bu değere göre modu alındığında Long Long sorunu ortadan kalkıyor.
#include <algorithm>
#include <stdio.h>
using namespace std;
typedef long long LL;
LL T,n,mod;
LL getpow4(LL x)
{
x%=mod;
x=(x*x)%mod;
x=(x*x)%mod;
return x;
}
LL sumpow4(LL x)
{
x%=mod*30;
LL a=x,b=x+1,c=2*x+1,d=3*x*x+3*x-1;
bool ok[3]={0,0,0};
if(a%2==0 && !ok[0]) { a/=2; ok[0]=1; }
if(a%3==0 && !ok[1]) { a/=3; ok[1]=1; }
if(a%5==0 && !ok[2]) { a/=5; ok[2]=1; }
if(b%2==0 && !ok[0]) { b/=2; ok[0]=1; }
if(b%3==0 && !ok[1]) { b/=3; ok[1]=1; }
if(b%5==0 && !ok[2]) { b/=5; ok[2]=1; }
if(c%2==0 && !ok[0]) { c/=2; ok[0]=1; }
if(c%3==0 && !ok[1]) { c/=3; ok[1]=1; }
if(c%5==0 && !ok[2]) { c/=5; ok[2]=1; }
if(d%2==0 && !ok[0]) { d/=2; ok[0]=1; }
if(d%3==0 && !ok[1]) { d/=3; ok[1]=1; }
if(d%5==0 && !ok[2]) { d/=5; ok[2]=1; }
a%=mod;
b%=mod;
c%=mod;
d%=mod;
return (((((a*b)%mod)*c)%mod)*d)%mod;
}
int main()
{
scanf("%lld",&T);
while(T--)
{
scanf("%lld%lld",&n,&mod);
LL kok=1;
while(kok*kok<=n) kok++;
kok--;
LL ans=0;
for(LL i=1 ; i<=kok ; i++)
{
LL a=(n/i)%mod;
LL b=getpow4(i);
ans=(ans+(a*b)%mod)%mod;
}
for(LL i=1 ; i<=kok ; i++)
{
LL a=sumpow4(n/i);
LL b=sumpow4(n/(i+1));
LL add=(a-b+mod)%mod;
add=(add*(i%mod))%mod;
ans=(ans+add)%mod;
}
if(n/kok==kok)
{
LL i=kok;
LL neg=getpow4(i);
neg=(neg*(i%mod))%mod;
ans=(ans-neg+mod)%mod;
}
printf("%lld\n",ans);
}
return 0;
}
Hiç yorum yok:
Yorum Gönder