In IIS, I created a new rule:

Then in the next dialog, I added a Pattern categories_page with conditions for {QUERY_STRING}
matching pattern c=(\d+)&p=(\d+)
(though you may not need a query string - customize per your needs). And for the Action I added a Rewrite URL of category{C:1}_pageid{C:2}.html
. If you don't need the query string, then you can un-check that checkbox for append query string.

Looking at the web.config file for the site, I see the XML below:
<?xml version="1.0" encoding="UTF-8"?>
<configuration>
<system.webServer>
<rewrite>
<rules>
<rule name="category-page">
<match url="categories_page" />
<action type="Rewrite" url="category{C:1}_pageid{C:2}.html" />
<conditions>
<add input="{QUERY_STRING}" pattern="c=(\d+)&p=(\d+)" />
</conditions>
</rule>
</rules>
</rewrite>
</system.webServer>
</configuration>
When trying this in my browser, I see the category1_pageid2.html page when I naveigate to localhost/categories_page?c=1&p=2
:

Other options include a rewrite map - see this answer for a short explanation.