网站公司是做什么的,抖音logo在线设计生成器免费,云空间免费空间,多种手机网站建设前言
我只是凑数的。 正题 输入输出#xff08;建议无视#xff09;
Input 第1行包含一个整数n。第2行包含一个整数M。第3行到第n2行#xff0c;每行包含两个整数#xff0c;分别表示ki和pi。两个整数之间用一个空格隔开。第3行的数据对应i1#xff0c;第n2行的数据对应…前言
我只是凑数的。 正题 输入输出建议无视
Input 第1行包含一个整数n。第2行包含一个整数M。第3行到第n2行每行包含两个整数分别表示ki和pi。两个整数之间用一个空格隔开。第3行的数据对应i1第n2行的数据对应in。
Output
仅一行包含一个整数表示方程的整数解的个数。
Sample Input
3 150 1 2 -1 2 1 2
Sample Output
178 解题思路
听真正的dalao讲的神奇幂伟大概就是把方程分成两半如
k1xp11k2xp22−k3xp33−k4xp44k1x1p1k2x2p2−k3x3p3−k4x4p4
k_1x_1^p1+k_2x_2^p2=-k_3x_3^p3-k_4x_4^p4 然后用深搜前半段找出第一个的所有答案存进哈希表里并且记录出现次数然后再搜一次后半段寻找与前半段答案相反的话就算上方案代码
#includecstdio
using namespace std;
const int maxn4000037;//哈希个数
int n,m,hash[maxn],mid,a[7],p[7],num[maxn],S,ans;
int abs(int x)
{if (x0) return -x;else return x;
}//绝对值定位时使用
int hashmath(int x)
{return abs(x)%maxn;}//哈希函数
int locate(int x)//定位用
{int i0,whashmath(x);//哈希函数while (imaxn hash[(wi)%maxn]!0 hash[(wi)%maxn]!x)i;//找到位置return (wi)%maxn;//返回位置
}
void ins(int x)//加入
{int wlocate(x);//定位hash[w]x;//改变值num[w];//记录出现次数
}
bool find(int x)//查找
{int wlocate(x);//位置if (hash[w]x) return true;//返回else return false;
}
void dfs(int dep,int sum)//第一次搜
{if (depmid1){ins(sum);//插入return;}for (int i1;im;i){ansi;for (int j2;jp[dep];j) ans*i;//即使x^pans*a[dep];//得出结果dfs(dep1,sumans);//搜}
}
void dfs2(int dep,int sum)
{if (depn1){if (find(-sum)) Snum[locate(-sum)];//如果找到就记录return;}for (int i1;im;i){ansi;for (int j2;jp[dep];j) ans*i;ans*a[dep];dfs2(dep1,sumans);}
}
int main()
{scanf(%d%d,n,m);for (int i1;in;i){scanf(%d%d,a[i],p[i]);}midn/2;//分成两段dfs(1,0);dfs2(mid1,0);printf(%d,S);
}
