sa1378
جمعه 30 آبان 1393, 11:26 صبح
فرض کنید gcd برابر 3 باشه
اولین عنصر لیست x را می کشیم بیرون و به عناصر اول تجزیه می کنیم
مثلا میشه 2 3 5 7
تابع T هم تعداد عناصری از لیست y را میده که به پارامتر تابع T بخشپذیر باشند که خیلی راحت با یک جمع و ضرب به دست میاد
باید T ها بزرگتر و مساوی 3 بدست بیاد
سپس T ها را اینجور با هم جمع می کنیم
T(3)-T(3*5)-T(3*7)+T(3*5*7) = T(3)-T(15)-(21)+T(105)
این برای عنصر اول، برای عناصر بعدی x هم همینطور ادامه می دهیم
اول بازه ها رو به d تقسیم کن این طوری فقط کافیه اعدادی که نسبت به هم اول هستن رو پیدا کنی
برای هر x تمام عامل های اول رو حساب کن (چون n تا تست کیس هست باید ذخیره هم بشن )
با استفاده از این رابطه (http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle)http://upload.wikimedia.org/math/0/7/1/0719353c1c4a12748b1f2efb85a49255.png
تمام زیر مجموعه های شامل 1 عضو اول 2 عضو اول و ... رو بسازو اونای که در بازه y هستن رو نگه دار .
تعداد میشه سایز کل حالت ها - سایز مجموعه های 1 عضوی +سایز مجموعه های 2 عضوی - سایز مجموعه های 3 عضوی و ...
از هردوتون ممنون
من راه حل آقای rahnema1 رو رفتم چون ساده تر بود یکم
ولی الان نمیدونم چجوری باید تابع calc رو توی کدم پیاده سازی کنم
(calc همون قسمتی هست که باید اینو حساب میکرد):
T(3)-T(3*5)-T(3*7)+T(3*5*7) = T(3)-T(15)-(21)+T(105)
کدی هم که زدم اینه:
#include <iostream>
#include <vector>
using namespace std;
int x1,x2,y1,y2,d,memT[1000*1000],ans;
bool mark[1000*1000];
vector <int> div;
void tajzie(int x)
{
for(int i=2;i*i<=x;i++)
{
while(x%i==0)
{
div.push_back(i);
x/=i;
}
}
if(x!=1)
div.push_back(x);
}
int T(int x)
{
int p=0;
if(mark[x]==true)
return memT[x];
mark[x]=true;
for(int i=y1;i<=y2;i++)
if(i%x==0)
p++;
return p;
}
int calc()
{
int end=div.size();
}
int main() {
int t;
cin>>t
for(int i=0;i<t;i++)
{
cin>>x1>>x2>>y1>>y2>>d;
for(int j=x1;j<=x2;j++)
{
if(j%d==0)
{
tajzie(j/d);
ans+=calc();
div.erase();
}
}
cout<<ans<<endl;
}
return 0;
}